排序是计算机内经常进行的一种操作，其目的是将一组“无序”的数据元素调整为“有序”的数据元素。常用的排序算法有选择排序、插入排序、冒泡排序、希尔排序、归并排序、快速排序、交换排序等。
1. 选择排序
基本思想：每一趟（例如第 i 趟，i = 0, 1, ..., n-2）在后面 n-i 个带排序的数据元素中选出关键字最小的元素，作为有序元素序列的第 i 个元素
时间复杂度：O(n^2)
空间复杂度：O(1)
是否稳定：不稳定
示例代码：
void Swap(int array[], int k, int i) { int temp = array[i]; array[i] = array[k]; array[k] = temp; } int SelectSort(int a[], int len) { int i = 0, j = 0, k = -1; for(i = 0; i < len; i++) { k = i; for(j = i + 1; j < len; j++) { if(a[k] > a[j]) { k = j; } } Swap(a, k, i); } return 0; }
2. 插入排序
基本思想：当插入第 i（i >= 1）个元素时，前面的V[0], V[1], ..., V[i-1]已经排好序，这是，用V[i]的关键字与V[i-1], V[i-2], ... 的关键字进行比较，找到插入位置即将V[i]插入，原来位置上的对象向后顺移。
时间复杂度：O(n^2)
空间复杂度：O(1)
是否稳定：稳定
示例代码：
int InsertSort(int a[], int len) { int i = 0, j = 0, k = -1; int temp = 0; for(i = 1; i < len; i++) { k = i; temp = a[k]; for(j = i - 1; (j >= 0) && (a[j] > temp); j--) { a[j+1] = a[j]; k = j; } a[k] = temp; } return 0; }
3. 冒泡排序
基本思想：设待排序数据元素序列中的元素个数为n，最多做 n-1 趟，i = 1, 2, ..., n-1。在第 i 趟中从后向前， j = n-1, n-2, ..., i，两两比较V[j-1]和V[j]的关键字。如果发生逆序，则交换V[j-1]和V[j]
时间复杂度：O(n^2)
空间复杂度：O(1)
是否稳定：稳定
示例代码：
void Swap(int array[], int k, int i) { int temp = array[i]; array[i] = array[k]; array[k] = temp; } int BubbleSort(int a[], int len) { int i = 0, j = 0, k = -1; int temp = 0; for(i = 0; i < len - 1; i++) { for(j = i; j < len - i - 1; j++) { if(a[j] > a[j+1]) { Swap(a, j, j + 1); } } } return 0; }
4. 希尔排序
基本思想：将待排序序列划分为若干组，在每一组内进行插入排序， 以使整个序列基本有序，然后再对整个序列进行插入排序
时间复杂度：O(n*logn)
空间复杂度：O(1)
是否稳定：不稳定
示例代码：
void swap(int array[], int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } void ShellSort(int array[], int len) // O(n*n) { int i = 0; int j = 0; int k = -1; int temp = -1; int gap = len; do { gap = gap / 3 + 1; for(i=gap; i<len; i+=gap) { k = i; temp = array[k]; for(j=i-gap; (j>=0) && (array[j]>temp); j-=gap) { array[j+gap] = array[j]; k = j; } array[k] = temp; } }while( gap > 1 ); }
5. 快速排序
基本思想：将待排序序列划分为若干组，在每一组内进行插入排序， 以使整个序列基本有序，然后再对整个序列进行插入排序
时间复杂度：O(n*logn)
空间复杂度：O(1)
是否稳定：不稳定
示例代码：
void swap(int array[], int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } int partition(int array[], int low, int high) { int pv = array[low]; while( low < high ) { while( (low < high) && (array[high] >= pv) ) { high--; } swap(array, low, high); while( (low < high) && (array[low] <= pv) ) { low++; } swap(array, low, high); } return low; } void QSort(int array[], int low, int high) { if( low < high ) { int pivot = partition(array, low, high); QSort(array, low, pivot-1); QSort(array, pivot+1, high); } } void QuickSort(int array[], int len) // O(n*logn) { QSort(array, 0, len-1); }
6. 归并排序
基本思想：每一趟（例如第 i 趟，i = 0, 1, ..., n-2）在后面 n-i 个带排序的数据元素中选出关键字最小的元素，作为有序元素序列的第 i 个元素
时间复杂度：O(n*logn)
空间复杂度：O(1)
是否稳定：稳定
示例代码:
void swap(int array[], int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } void Merge(int src[], int des[], int low, int mid, int high) { int i = low; int j = mid + 1; int k = low; while( (i <= mid) && (j <= high) ) { if( src[i] < src[j] ) { des[k++] = src[i++]; } else { des[k++] = src[j++]; } } while( i <= mid ) { des[k++] = src[i++]; } while( j <= high ) { des[k++] = src[j++]; } } void MSort(int src[], int des[], int low, int high, int max) { if( low == high ) { des[low] = src[low]; } else { int mid = (low + high) / 2; int* space = (int*)malloc(sizeof(int) * max); if( space != NULL ) { MSort(src, space, low, mid, max); MSort(src, space, mid+1, high, max); Merge(space, des, low, mid, high); } free(space); } } void MergeSort(int array[], int len) // O(n*logn) { MSort(array, array, 0, len-1, len); }
7. 交换排序
前提条件：一组1, 2, ... , n数组，各个元素不能重复。
基本思想：通过交换，把a[0] = 1, a[1] = 2, ... , a[n-1] = n
时间复杂度：O(n)
空间复杂度：O(1)
示例代码：
int SwapSort(int a[], int len) { int i = 0; int temp = 0; for(i = 0; i < len;) { temp = a[a[i] - 1]; a[a[i] - 1] = a[i]; a[i] = temp; if(a[i] == i + 1) { i++; } } return 0; }