1 常見(jiàn)的排序算法

排序算法概況-菜鳥(niǎo)教程

2 實(shí)現(xiàn)方法

2.1 冒泡排序

步驟思路： 比較相鄰的元素，如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)，再比較交換后的第二個(gè)和第三個(gè)，直到最大的一個(gè)元素到最后。

菜鳥(niǎo)教程-動(dòng)圖演示

#include <iostream>
using namespace std;
int main() {
  int arr[] = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};
  int len = (int) sizeof(arr) / sizeof(*arr);
  // 冒泡排序
  for (int i=0; i<len-1; i++) {
    for (int j=0; j<len-1-i; j++){
      if (arr[j] > arr[j+1]) {
        int temp = arr[j];
        arr[j] = a[j+1];
        arr[j+1] = temp;
      }
    }
  }
  for (int i=0; i<len; i++) {
    cout<<arr[i] << ' ';
  }
}

2.2 選擇排序

步驟思路：首先在未排序序列中找到最大（?。┰?，存放到排序序列的起始位置，再?gòu)氖Ｓ嗟奈磁判虻脑刂欣^續(xù)尋找最大（小）的元素，放到已排序序列的末尾。
相當(dāng)于將序列分為兩部分，在未排序的部分選擇符合規(guī)則的元素，放到有序的部分。

菜鳥(niǎo)教程-動(dòng)圖演示

#include<iostream>
using namespace std;
int main() {
  int arr[] = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};
  // 選擇排序
  for (int i=0; i<arr.size()-1; i++) {
    int min = i;
    for(int j=i+1; j<arr.size(); j++) {
      if (arr[j] < arr[min])
        min = j;
    }
    swap(arr[i], arr[min]);
  }
}

2.3 插入排序

步驟思路：還是將整個(gè)序列看成兩部分，已經(jīng)有序部分和待排序部分，從頭到尾依次掃描未排序序列，將掃描的元素插入到有序序列的適當(dāng)位置。（相同大小往后放）

菜鳥(niǎo)教程-動(dòng)圖演示

#include<iostream>
using namespace std;
int main() {
  int arr[] = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};
  // 插入排序
  for (int i=1; i<arr.size(); i++) {
    int key = arr[i];
    int j = i-1;
    while((j>=0) && (key<arr[j])) {
      arr[j+1] = arr[j];
      j--;
    }
    arr[j+1] = key;
  }
}

2.4 歸并排序

步驟思路：

• 申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列；
• 設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置；
• 比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置；
• 重復(fù)步驟 3 直到某一指針達(dá)到序列尾；

• 將另一序列剩下的所有元素直接復(fù)制到合并序列尾。

  
  
  菜鳥(niǎo)教程-動(dòng)圖演示

// 迭代法
template<typename T>
void merge_sort(T arr[], int len) {
    T *a = arr;
    T *b = new T[len];
    for (int seg = 1; seg < len; seg += seg) {
        for (int start = 0; start < len; start += seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        T *temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        for (int i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    delete[] b;
}

// 遞歸法
void Merge(vector<int> &Array, int front, int mid, int end) {
    // preconditions:
    // Array[front...mid] is sorted
    // Array[mid+1 ... end] is sorted
    // Copy Array[front ... mid] to LeftSubArray
    // Copy Array[mid+1 ... end] to RightSubArray
    vector<int> LeftSubArray(Array.begin() + front, Array.begin() + mid + 1);
    vector<int> RightSubArray(Array.begin() + mid + 1, Array.begin() + end + 1);
    int idxLeft = 0, idxRight = 0;
    LeftSubArray.insert(LeftSubArray.end(), numeric_limits<int>::max());
    RightSubArray.insert(RightSubArray.end(), numeric_limits<int>::max());
    // Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight], and put into Array[i]
    for (int i = front; i <= end; i++) {
        if (LeftSubArray[idxLeft] < RightSubArray[idxRight]) {
            Array[i] = LeftSubArray[idxLeft];
            idxLeft++;
        } else {
            Array[i] = RightSubArray[idxRight];
            idxRight++;
        }
    }
}

void MergeSort(vector<int> &Array, int front, int end) {
    if (front >= end)
        return;
    int mid = (front + end) / 2;
    MergeSort(Array, front, mid);
    MergeSort(Array, mid + 1, end);
    Merge(Array, front, mid, end);
}

2.5 快速排序

步驟思路：從序列中挑選一個(gè)元素作為基準(zhǔn)，重新排序，比基準(zhǔn)小的放前面， 比基準(zhǔn)大的放右邊。
遞歸把小于基準(zhǔn)值元素子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。

菜鳥(niǎo)教程-動(dòng)圖演示

// 迭代法
struct Range {
    int start, end;
    Range(int s = 0, int e = 0) {
        start = s, end = e;
    }
};
template <typename T> 
void quick_sort(T arr[], const int len) {
    if (len <= 0)
        return; // 避免len等於負(fù)值時(shí)宣告堆疊陣列當(dāng)機(jī)
    // r[]模擬堆疊,p為數(shù)量,r[p++]為push,r[--p]為pop且取得元素
    Range r[len];
    int p = 0;
    r[p++] = Range(0, len - 1);
    while (p) {
        Range range = r[--p];
        if (range.start >= range.end)
            continue;
        T mid = arr[range.end];
        int left = range.start, right = range.end - 1;
        while (left < right) {
            while (arr[left] < mid && left < right) left++;
            while (arr[right] >= mid && left < right) right--;
            std::swap(arr[left], arr[right]);
        }
        if (arr[left] >= arr[range.end])
            std::swap(arr[left], arr[range.end]);
        else
            left++;
        r[p++] = Range(range.start, left - 1);
        r[p++] = Range(left + 1, range.end);
    }
}

// 遞歸法
template <typename T>
void quick_sort_recursive(T arr[], int start, int end) {
    if (start >= end)
        return;
    T mid = arr[end];
    int left = start, right = end - 1;
    while (left < right) { //在整個(gè)范圍內(nèi)搜尋比樞紐元值小或大的元素，然后將左側(cè)元素與右側(cè)元素交換
        while (arr[left] < mid && left < right) //試圖在左側(cè)找到一個(gè)比樞紐元更大的元素
            left++;
        while (arr[right] >= mid && left < right) //試圖在右側(cè)找到一個(gè)比樞紐元更小的元素
            right--;
        std::swap(arr[left], arr[right]); //交換元素
    }
    if (arr[left] >= arr[end])
        std::swap(arr[left], arr[end]);
    else
        left++;
    quick_sort_recursive(arr, start, left - 1);
    quick_sort_recursive(arr, left + 1, end);
}
template <typename T>
void quick_sort(T arr[], int len) {
    quick_sort_recursive(arr, 0, len - 1);
}

OJ技巧

在進(jìn)行OJ的時(shí)候要善于對(duì)于復(fù)雜的數(shù)據(jù)形式利用結(jié)構(gòu)體和sort函數(shù)，定義比較規(guī)則。
舉個(gè)例子，對(duì)學(xué)生信息（包括姓名、年齡、成績(jī)）進(jìn)行排序

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

struct E {
  char name[101];
  int age;
  int score;
}buf[1000];
// 實(shí)現(xiàn)比較規(guī)則
bool cmp(E a, E b) {
  // 分?jǐn)?shù)不同，分?jǐn)?shù)低的在前
  if(a.score != b.score)
    return a.score < b.score;
  int tmp = strcmp(a.name, b.name);
  // 分?jǐn)?shù)相同，名字字典在前的在前
  if (tmp != 0)
    return tmp < 0;
  else 
    // 名字相同，年齡小的在前
    return a.age < b.age
}
int main() {
  int n;
  while(scanf (%d, &n) != EOF) {
    for (int i=0; i<n; i++) {
      cin >> buf[i].name >> &buf[i].age, &buf[i].score;
    }
    // 利用自己定義的規(guī)則排序
    sort(buf, buf+n, cmp);
    for(int i=0; i<n; i++) {
      cout<<buf[i].name<<buf[i].age<<buf[i].score<< endl;
    }
  }
return 0;
}