正文

常用术语说明

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；

内排序：所有排序操作都在内存中完成；
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；

时间复杂度: 一个算法执行所耗费的时间。
空间复杂度: 运行完一个程序所需内存的大小。

排序分类

对于我这种只是想简单了解一下排序算法的人来说，这6种（冒泡排序、快速排序、简单选择排序、直接插入排序、堆排序和希尔排序）算法的学习就已经足够了。

算法介绍（全部以C语言的形式介绍）

int array[] = {6 ,1 ,2 ,7 ,9 ,3 ,4 ,5 ,10 ,8};
int num = sizeof(array)/sizeof(int);

冒泡排序（Bubble Sort）
人生中接触的第一种排序方法。

算法描述
通过交换使相邻的两个数变成小数在前大数在后，这样每次遍历后，最大的数就“沉”到最后面了。重复N次即可以使数组有序。

算法实现

  for (int i = 0; i < num - 1; i++) {
      for (int j = 0; j < num - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
            int tmp = array[j];
            array[j] = array[j + 1];
            array[j + 1] = tmp;
          }
      }
  }

快速排序（Quick Sort）

算法描述

1.在待排序的元素任取一个元素作为基准(通常选第一个元素，但最的选择方法是从待排序元素中随机选取一个作为基准)，称为基准元素；

2.将待排序的元素进行分区，比基准元素大的元素放在它的右边，比其小的放在它的左边；

3.对左右两个分区重复以上步骤直到所有元素都是有序的。

所以我是把快速排序联想成东拆西补或西拆东补，一边拆一边补，直到所有元素达到有序状态。

算法实现

  void sort(int *a,int left,int right) {
      if (left >= right) {
          return;
      }
    // 由于已经将a[0]中的数保存到key中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。
    // 从j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++;  这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数，当i=3，符合条件，将a[3]挖出再填到上一个坑中a[8]=a[3]; j--;
   
      int i = left;
      int j = right;
      int key = a[i]; //a[i]就是第一个坑
    
      while (i < j) {
          // 从右向左找小于x的数来填s[i]
          while (i < j && key <= a[j]) {
              j--;
          }
          a[i] = a[j];
          while (i < j && key >= a[i]) {
              i++;
          }
          a[j] = a[i];
      }
      a[i] = key;
      sort(a, left, i-1);
      sort(a, i+1, right);
  }

还有一种比较个性理解的版本:一次循环先交换大小的，最后才和基数的交换。

在博客坐在马桶上看算法：快速排序看到的，评论区各种吵架，说这不是快排。感觉思路是一样的。代码如下

  void sort1(int *a,int left,int right) {
      if (left >= right) {
          return;
      }
      int i = left;
      int j = right;
      int key = a[i];
    
      while (i != j) {
          //顺序很重要，要先从右边开始找
          while (i < j && key <= a[j]) {
              j--;
          }
          //再找左边的
          while (i < j && key >= a[i]) {
              i++;
          }
          //交换两个数在数组中的位置
          if(i < j){
              int t=a[i];
              a[i]=a[j];
              a[j]=t;
          }
      }
      //最终将基准数归位
      a[left]=a[i];
      a[i]=key;
      sort1(a, left, i-1);
      sort1(a, i+1, right);
}