排序算法¶

一种将一组特定的数据按某种顺序进行排列的算法

稳定性¶

稳定排序

如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序。
非稳定排序

如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。

内外排序¶

内排序，不适用额外的空间
外排序，需要使用额外的空间

冒泡排序¶

两两比较相邻的记录的关键字，如果反序则交换，直到没有反序的记录为止。
sort

假如有n(n>2)个数进行排序

第几轮比较	处理数个数	比较次数	说明
1	n	n-1	第一次比较，n个数从左往右两辆比较，需要比较n-1次
2	n-1	n-2	第一次处理完后，还有n-1个数需要比较，需要比较n-2次
...	...	...	...
n-1	2	1	第n-1次，剩下2个数，只需要比较1次
n	1	0	只剩下一个数，不需要比较，比较次数为0

通过上述分析可以得到：
n(n>1)个数排序,一共需要处理n-1轮
每k(k<=n)轮需要比较n-k次
当某一轮处理完后没发生交换时，说明已全部有序，则可结束排序

C
//从小到大排列示例
//数组a[n] n>=1
void bubbleSort(int *a, int n) {
    if (a == NULL || n < 2)
        return;
  int t = n - 1;     //n个数需要比较n-1轮
  int flag = 1;  //某一轮是否有交换
  while(t && flag) {
    flag = 0;
    for(int i = 0; i < t; i++) { //依次比较未排序的数列
      if(a[i] > a[i+1]) {
        swap(a, i, i+1);
        flag = 1; //本轮发生交换
      }
    }
    t--;
}

选择排序¶

从未排序的记录里选择最小(大)的元素，放到有序记录后
sort

C
//选择排序
void selectSort(int *a, int n) {
    if (a == NULL || n < 2)
        return;
    int min;
    for(int i = 0; i < n-1; i++) {
        min = i;  //记录当前索引
        for(int j = i+1; j < n; j++) {
            if(a[min] > a[j])
            {
                min = j; //记录最小索引
            }
        }
        if(min != i)
            swap(a,i,min); //最小值索引发生变化，更换
    }
}

插入排序¶

将未排序的记录依次插入到已排序的记录内。
sort

C
//插入排序
void insertsort(int *a ,int n) {
    for(int i = 1; i < n; i++) { //从第一个元素开始比较
        for(int j = i; j > 0; j--) { //往前依次插入
            if(a[j] < a[j-1]) { //次序不对依次交换
               swap(a, j, j-1);
            }
            else
                break; //不用交互，跳出
        }
    }
}

希尔排序¶

归并排序¶

先将数组拆分成两个子数组
然后分别对两个子数组排序
最后将两个子数组合并成一个有序数组
sort 拆分的过程将调用递归实现。

C
//归并排序
void merge(int *a, int left, int mid, int right) {
    int *tmp = (int *)malloc(sizeof(int)*(right - left + 1));
    int i = o, j = left, k = mid + 1;
    while(j <= mid && k <= right) {
        if(a[j] < a[k]) {
            tmp[i++] = a[j++];
        }
        else {
            tmp[i++] = a[k++];
        }
    }

    while(j <= mid) {
        tmp[i++] = a[j++];
    }
    while(k <= right) {
        tmp[i++] = a[k++];
    }
    for(i = 0; i < right - left + 1; i++) {
        a[left + i] = tmp[i];
    }
    free(b);
}
void mergeSort(int *a, int left, int right) {
    if(left < right) {
        int mid = (left + right) / 2;
        mergeSort(a, left, mid);
        mergeSort(a, mid + 1, right);
        merge(a, left, mid, right);
    }
}

快速排序¶

从数列里随机挑选一个元素作为基准（pivot）
遍历数列，使其左边的数比基准小，右边的比基准大
然后在两个子数列内重复上述步骤
sort

C
/* 快排算法 */
void quicksort(int* A, int low, int high) {
  //检查索引
  if( low >= high || low < 0 ) 
    return;

  //分割数组并返回基准位
  int p = partition(A, low, high); 

  //对分割的两个段进行排序
  quicksort(A, low, p - 1); //基准左边的段
  quicksort(A, p + 1, high); //基准右边的段
}

/* 分割算法 */
int partition(A, low, high) {
  int pivot := A[high] //将最后一个元素作为基准位

  // Temporary pivot index
  int i = low - 1;

  for(int j = low; j < high; j++) { 
    if (A[j] <= pivot)
      i = i + 1;

      // Swap the current element with the element at the temporary pivot index
      swap(A[i],A[j]); 
  // Move the pivot element to the correct pivot position (between the smaller and larger elements)
  i = i + 1;
  swap(A[i],A[high]);
  }
  return i; //返回基准索引
}

堆排序¶

sort

计数排序¶

sort

桶排序¶

基数排序¶

sort

排序算法时间复杂度¶

time