常见的8种排序（含代码）：插入排序、冒泡排序、希尔排序、快速排序、简单选择排序、归并排序、堆排序、基数排序

时间复杂度O(n^2)

1、插入排序 (Insertion Sort)

        从第一个元素开始，该元素可以认为已经被排序；取出下一个元素，在已经排序的元素序列中从后向前扫描；如果该元素（已排序）大于新元素，将该元素移到下一位置；重复步骤，直到找到已排序的元素小于或者等于新元素的位置；将新元素插入到该位置后。

void insertionSort(int arr[], int n) {  for (int i = 1; i < n; ++i) {  int key = arr[i];  int j = i - 1;  while (j >= 0 && arr[j] > key) {  arr[j + 1] = arr[j];  --j;  }  arr[j + 1] = key;  }  
}

2、冒泡排序 (Bubble Sort)

        重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

void bubbleSort(int arr[], int n) {  for (int i = 0; i < n - 1; ++i) {  for (int j = 0; j < n - i - 1; ++j) {  if (arr[j] > arr[j + 1]) {  std::swap(arr[j], arr[j + 1]);  }  }  }  
}

3、简单选择排序 (Selection Sort)

        每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

void selectionSort(int arr[], int n) {  for (int i = 0; i < n - 1; i++) {  int min_idx = i;  for (int j = i + 1; j < n; j++) {  if (arr[j] < arr[min_idx]) {  min_idx = j;  }  }  std::swap(arr[min_idx], arr[i]);  }  
}  

时间复杂度O(nlog2n)

4、希尔排序(Shell Sort)

        是插入排序的一种又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法的基本思想是：先将整个待排序的记录序列分割成为若干子序列（由相隔某个“增量”的记录组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
（这里只给出增量的简化选择，实际应用中增量序列的选择会更复杂）

void shellSort(int arr[], int n) {  int gap = n / 2;  while (gap > 0) {  for (int i = gap; i < n; ++i) {  int temp = arr[i];  int j = i;  while (j >= gap && arr[j - gap] > temp) {  arr[j] = arr[j - gap];  j -= gap;  }  arr[j] = temp;  }  gap /= 2;  }  
}

5、快速排序(Quick Sort)

        通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

int partition(int arr[], int low, int high) {  int pivot = arr[high];  int i = (low - 1);  for (int j = low; j <= high - 1; j++) {  if (arr[j] < pivot) {  i++;  std::swap(arr[i], arr[j]);  }  }  std::swap(arr[i + 1], arr[high]);  return (i + 1);  
}  void quickSort(int arr[], int low, int high) {  if (low < high) {  int pi = partition(arr, low, high);  quickSort(arr, low, pi - 1);  quickSort(arr, pi + 1, high);  }  
}

6、堆排序(Heap Sort)

        堆排序是利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。堆排序主要要解决两个问题：

        1）如何根据给定的序列建初始堆

         2）如何在交换掉根结点后，将剩下的结点调整为新的堆(筛选)

void set(int p,int m){//小顶堆int i,j;i=p;j=i*2;while(j<=m){if(j<=m-1&&k[j]>k[j+1])//改为<j++;if(k[j]>=k[i])//改为<=，则为大顶堆break;else{swap(k[i],k[j]);i=j;j=i*2;}}
}void heapSort(){int i,j;for(i=n/2;i>0;i--)//建堆set(i,n);for(i=n;i>1;i--)//排序{swap(k[i],k[1]);set(1,i-1);}
}

7、归并排序 (Merge Sort)

        归并排序采用分治法的思想，将数组分成两半，分别对它们进行排序，然后将结果合并起来。

        1）编写一个辅助函数来合并两个已排序的子数组。

        2）编写主归并排序函数，该函数将递归地分解数组，直到子数组只包含一个元素（已排序），然后合并这些子数组，直到整个数组排序完成。

void merge(int arr[], int left[], int leftSize, int right[], int rightSize) {  int i = 0, j = 0, k = 0;  while (i < leftSize && j < rightSize) {  if (left[i] <= right[j]) {  arr[k++] = left[i++];  } else {  arr[k++] = right[j++];  }  }  while (i < leftSize) {  arr[k++] = left[i++];  }  while (j < rightSize) {  arr[k++] = right[j++];  }  
}  void mergeSort(int arr[], int left, int right) {  if (left < right) {  int mid = left + (right - left) / 2;  int leftSize = mid - left + 1;  int rightSize = right - mid;  int leftArr[leftSize], rightArr[rightSize];  // 拷贝数据到临时数组  for (int i = 0; i < leftSize; i++) {  leftArr[i] = arr[left + i];  }  for (int j = 0; j < rightSize; j++) {  rightArr[j] = arr[mid + 1 + j];  }  // 递归地对子数组进行排序  mergeSort(leftArr, 0, leftSize - 1);  mergeSort(rightArr, 0, rightSize - 1);  // 合并两个已排序的子数组  merge(arr, leftArr, leftSize, rightArr, rightSize);  }  
}  

时间复杂度O(d(n+rd))

8、基数排序(Radix Sort)

        基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。为了适用于负数和非整数，这里给出一个简化的版本，仅适用于非负整数，并且假设所有整数的位数相同（或可以通过填充前导零来使它们具有相同的位数）。

#include <vector>  
#include <algorithm>  void countingSort(std::vector<int>& arr, int exp) {  std::vector<int> output(arr.size());  std::vector<int> count(10, 0);  // 存储每个桶中的元素数量  for (int i = 0; i < arr.size(); i++)  count[(arr[i] / exp) % 10]++;  // 更改count[i]，使其包含每个数字小于或等于i的数量  for (int i = 1; i < 10; i++)  count[i] += count[i - 1];  // 构建输出数组  for (int i = arr.size() - 1; i >= 0; i--) {  output[count[(arr[i] / exp) % 10] - 1] = arr[i];  count[(arr[i] / exp) % 10]--;  }  // 复制回原数组  for (int i = 0; i < arr.size(); i++)  arr[i] = output[i];  
}  void radixsort(std::vector<int>& arr) {  int maxVal = *std::max_element(arr.begin(), arr.end());  // 找到最大数的位数  int exp = 1;  while (maxVal / exp > 0) {  countingSort(arr, exp);  exp *= 10;  }  
}  

或者

#include <iostream>  
#include <cmath>  
#include <algorithm> // 使用std::max来找到数组中的最大值  // 获取数组中的最大值  
int getMax(int arr[], int n) {  int mx = arr[0];  for (int i = 1; i < n; i++) {  if (arr[i] > mx) {  mx = arr[i];  }  }  return mx;  
}  // 基数排序函数  
void radixsort(int arr[], int n) {  // 找到数组中的最大值  int maxVal = getMax(arr, n);  // 基数排序使用计数排序作为子程序  // 这里为了简单起见，我们假设所有的整数都是非负的  // 如果有负数，需要做适当的转换  // 对每一位执行计数排序  for (int exp = 1; maxVal / exp > 0; exp *= 10) {  int output[n]; // 输出数组  int count[10] = {0}; // 计数器数组  // 存储每个元素的频次  for (int i = 0; i < n; i++) {  int index = (arr[i] / exp) % 10;  count[index]++;  }  // 更改count[i]的值，这样它现在包含位置i处之前的所有元素  for (int i = 1; i < 10; i++) {  count[i] += count[i - 1];  }  // 生成输出数组  for (int i = n - 1; i >= 0; i--) {  int index = (arr[i] / exp) % 10;  output[count[index] - 1] = arr[i];  count[index]--;  }  // 将排序后的元素复制回原数组  for (int i = 0; i < n; i++) {  arr[i] = output[i];  }  }  
}  int main() {  int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};  int n = sizeof(arr) / sizeof(arr[0]);  radixsort(arr, n);  std::cout << "Sorted array: \n";  for (int i = 0; i < n; i++) {  std::cout << arr[i] << " ";  }  std::cout << std::endl;  return 0;  
}