十大经典排序算法汇总

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

n：数据规模
k：”桶”的个数
In-place：占用常数内存，不占用额外内存
Out-place：占用额外内存
稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同

冒泡排序

#include <iostream>
using namespace std;
template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void bubble_sort(T arr[], int len) {
  int i, j;
  for (i = 0; i < len - 1; i++)
    for (j = 0; j < len - 1 - i; j++)
      if (arr[j] > arr[j + 1])
        swap(arr[j], arr[j + 1]);
}

选择排序

template<typename T> //整數或浮點數皆可使用，若要使用物件（class）時必須設定大於（>）的運算子功能
void selection_sort(std::vector<T>& arr) {
  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;
    std::swap(arr[i], arr[min]);
  }
}

插入排序

void insertion_sort(int arr[], int len){
  for(int i = 1; i < len; 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;
  }
}

希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录”基本有序”时，再对全体记录进行依次直接插入排序。

算法步骤

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

按增量序列个数 k，对序列进行 k 趟排序；

每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

template<typename T>
void shell_sort(T array[], int length) {
  int h = 1;
  while (h < length / 3) {
    h = 3 * h + 1;
  }
  while (h >= 1) {
    for (int i = h; i < length; i++) {
      for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
        std::swap(array[j], array[j - h]);
      }
    }
    h = h / 3;
  }
}

归并排序

自下而上迭代版本：

template<typename T> // 整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)的運算子功能
void merge_sort(T arr[], int len) {
    T *a = arr;
    T *b = new T[len];
  	// seg 步长，翻倍增长
    for (int seg = 1; seg < len; seg += 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++];
        }
      	// 交换a,b; 使用每次seg翻倍时都在上一次seg归并的基础上操作，最终a是有序的
        T *temp = a;
        a = b;
        b = temp;
    }
    // 因为a是有序的，如果a不是原数组，拷贝一次
    if (a != arr) {
        for (int i = 0; i < len; i++)
            b[i] = a[i];
      	// 最后delete掉额外使用的内存
        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;
  	// 巧妙运用max(),简化后续的处理
    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);
}

快速排序

算法步骤

从数列中挑出一个元素，称为 “基准”（pivot）;
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

挖坑法:

//严蔚敏《数据结构》标准分割函数
 Paritition1(int A[], int low, int high) {
   int pivot = A[low];
   // 反复查找、替换元素
   while (low < high) {
     // 从后往前找到第一个比pivot小的数，放到low位置
     while (low < high && A[high] >= pivot) {
       --high;
     }
     A[low] = A[high];
     // 从前往后找到第一个比pivot大的数，放到high位置
     while (low < high && A[low] <= pivot) {
       ++low;
     }
     A[high] = A[low];
   }
   // 最后空出来的是low位置
   A[low] = pivot;
   return low;
 }

 void QuickSort(int A[], int low, int high) //快排母函数
 {
   if (low < high) {
     int pivot = Paritition1(A, low, high);
     QuickSort(A, low, pivot - 1);
     QuickSort(A, pivot + 1, high);
   }
 }

左右指针法：

1．将数组的最后一个数right作为基准数key。（随机取一个数与right交换，达到随机化排序） 2．分区过程:从数组的首元素begin开始向后找比key大的数（begin找大）；end开始向前找比key小的数（end找小）；找到后然后两者交换（swap）,知道begin >= end终止遍历。最后将begin和最后一个数交换 3．再对左右区间重复第二步，直到各区间只有一个数。

int PartSort1(int* a,int left,int right)
{
    int begin = left;
    int end = right;
    int key = right;

  	// 循环终止时，begin == end
    while( begin < end )
    {
        //begin找大
        while(begin < end && a[begin] <= a[key])
        {
            ++begin;
        }
        //end找小
        while(begin < end && a[end] >= a[key])
        {
            --end;
        }
        swap(a[begin],a[end]);
    }
    swap(a[begin],a[right]);
    return begin;//返回的是中间的位置，swap只是交换值
}

int quickSort(int* a, int left, int right) {
  if (left >= right) return 0;
  int mid = PartSort1(a, left, right);
  quickSort(a, left, mid-1);
  quickSort(a, mid+1, right)
}

前后指针法：

定义两个指针，一前一后，cur（前）指向起始位置，prev（后）指向cur的前一个位置；选择数组最后一个元素作为key（right）
实现过程：cur找比key小的数，prev在cur没有找到的情况下，一直不动（即保证prev一直指向比key小的数）；直到cur找到比key小的数（++prev && prev != cur时）然后++cur, prev仍然不动。
直到cur走到right前一个位置，终止循环。最后++prev，交换prev和right的值。返回中间位置prev。最后再继续递归。

int PartSort3(int* a,int left,int right)
{
    int cur = left;
    int prev = left -1;
    int key = a[right];
  	// 终止时，cur == right
    while(cur < right)
    {
      	// 找到一个比key小的数，前移pre并交换
      	// 这一步保证a[0:prev]都是比key小的, a[prev+1:cur]都是比key大的
        if(a[cur] < key && ++prev != cur)
        {
            swap(a[cur],a[prev]);
        }
        ++cur;
    }
  	// 最后一次交换
    swap(a[++prev],a[right]);
    return prev;
}

int quickSort(int* a, int left, int right) {
  if (left >= right) return 0;
  int mid = PartSort3(a, left, right);
  quickSort(a, left, mid-1);
  quickSort(a, mid+1, right)
}

堆排序

算法步骤

创建一个堆 H[0……n-1]；
把堆首（最大值）和堆尾互换；
把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
重复步骤 2，直到堆的尺寸为 1。

#include <iostream>
#include <algorithm>
using namespace std;

// 调整arr[start:end] 使其成为最大堆
void max_heapify(int arr[], int start, int end) {
    // 建立父節點指標和子節點指標
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) { // 若子節點指標在範圍內才做比較
        if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比較兩個子節點大小，選擇最大的
            son++;
        if (arr[dad] > arr[son]) // 如果父節點大於子節點代表調整完畢，直接跳出函數
            return;
        else { // 否則交換父子內容再繼續子節點和孫節點比較
            swap(arr[dad], arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}

void heap_sort(int arr[], int len) {
    // 初始化，i從最後一個父節點開始調整
    for (int i = len / 2 - 1; i >= 0; i--)
        max_heapify(arr, i, len - 1);
    // 先將第一個元素和已经排好的元素前一位做交換，再從新調整(刚调整的元素之前的元素)，直到排序完畢
    for (int i = len - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}

计数排序

参考 https://www.runoob.com/w3cnote/ten-sorting-algorithm.html

桶排序

参考 https://www.runoob.com/w3cnote/ten-sorting-algorithm.html

基数排序

参考 https://www.runoob.com/w3cnote/ten-sorting-algorithm.html