排序问题作为计算机领域的基本问题，在计算机世界的每个角落都有着她的身影。一个合适的排序算法往往能够让一类算法问题的求解速度得到极大地提升。本文主要总结了常见的排序算法的基本原理和时间复杂度。

冒泡排序

冒泡排序的原理是每次遍历的过程中对相邻元素两两比较，若该元素对为逆序则交换位置。当一次遍历结束时，则原数列至少有一个元素排到了正确的位置。如此循环遍历数列，直到数列中不存在逆序对。实现如下：

1
2
3
4
5
6
7

void bubbleSort(int arr[], int n) {
  for (int i=0; i<n-1; i++) { //确定遍历次数
    for (int j=0; j<n-1-i; j++) { //确定比较次数
      if (arr[j] < arr[j+1]) swap(arr[j+1], arr[j]);
    }
  }
}

通过代码可以发现冒泡排序的算法时间复杂度为$O(n^2)$.冒泡排序的核心就是检测序列是否含有逆序对，一旦确定不包含逆序对时，那么序列就是有序的而无需再遍历和比较了。因此可以设定一个标志检测是否包含逆序对，改进实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

void bubbleSort(int arr[], int n) {
  for (int i=0; i<n-1; i++) { //确定遍历次数
    bool flag = true; //不包含逆序对
    for (int j=0; j<n-1-i; j++) { //确定比较次数
      if (arr[j] < arr[j+1]) {
        swap(arr[j+1], arr[j]);
        flag = false; 
      }

      if (flag) {
        return;
      }
    }
  }
}

以上优化的主要思想是提前结束对数组的遍历，但是对于遍历本身也可以进行优化。每次遍历中最后一次的交换位置之后的元素都已经有序无需再遍历，因此可以记下该位置作为下一次遍历的终点位置。实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

void bubbleSort(int arr[], int n) {
  int pos = 0; // 位置记录
  int k = n-1;
  bool flag = true; //不包含逆序对
  for (int i=0; i<n-1; i++) { //确定遍历次数
    flag = true; //不包含逆序对
    pos = 0;
    for (int j=0; j<k; j++) { //确定比较次数
      if (arr[j] < arr[j+1]) {
        swap(arr[j+1], arr[j]);
        flag = false; 
        pos = j;
      }
    }

    if (flag) {
      return;
    }
    k=pos;
  }
}

选择排序

选择排序的原理为每次遍历当前范围元素选择最小值与当前范围的第一个元素交换位置，如此第一个元素的位置就已经排好。此后再在第一个元素之后的范围重复该操作，遍历的范围逐次递减直至全部元素都已经排好位置。其实现如下：

1
2
3
4
5
6
7
8
9

void selectSort(int arr[], int n) {
  for (int i=0; i<n; i++) {
    int maxIndex = i;
    for (int j=i; j<n; j++) {
      if (arr[j] > arr[maxIndex]) maxIndex = j; 
    }
    swap(arr[i], arr[maxIndex]);
  }
}

遍历n次，每次遍历从i到n，因此算法复杂度也为$O(n^2)$.

插入排序

插入排序的原理是在数列的一端（以前端为例）维护有序数列，每次遍历时从无序数列中选择一个插入到前端的有序数列中。重复该操作直到无序数列为空，则原数列排好序。实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

void insertSort(int arr[], int n) {
  for (int i=1; i<n; i++) { //一个元素时不用循环，从第二个元素开始
    for (int j=i-1; j>=0; j--) {
      //if (arr[j+1] >= arr[j]) swap(arr[j+1], arr[j]); 
      //else break;
      //可以优化如下：
      int tmp = arr[i];
      if (arr[j] < tmp) {
        arr[j] = arr[j+1];
      } else {
        arr[j] = tmp;
        break;
      }
    }
  }
}

同样容易分析选择排序也是复杂度为$O(n^2)$的排序算法，但是在选择排序过程中程序可以提前终止遍历操作，因此在基本有序的数组中选择排序就有较好的性能。由此可以先将无序数组转化成基本有序数组再进行插入排序就可以得到插入算法的改进版本希尔排序。

希尔排序

将整个序列按照相距某个“增量”进行拆分，然后逐个对子序列进行直接插入排序，使得得到的结果基本有序，最后对基本有序的序列进行一次直接插入排序，使得整个序列有序。实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void shellSort(int arr[], int n) {
  for (int delta=n/2, delta>=1; delta/=2) { //拆分整个数组为元素间隔为delta的子数组
  //对每个子数组插入排序
    for (int i=delta; i<n; i++) {
      for (int j=i-delta; j>=0; j-=delta) {
        if (arr[j]>arr[j+delta]) swap(arr[j], arr[j+delta]);
      }
    }
  }
}

希尔排序的关键是将原数组按相隔一个增量delta距离的元素组成子序列，此处的增量十分关键，当前还找到最好的增量序列（本例中为n/2序列）。值得注意的是增量序列的最后一个增量值必须等于1。

归并排序

归并排序的原理为在对一个序列排序的时候，先将其（递归地）分为两半分别排序最后将结果归并起来，即将两个有序序列合并为一个有序序列。实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

void merge(int arr[], int l, int mid, int r) {
  int aux[r-l+1];
  for (int i=l; i<=r; i++) aux[i-l] = arr[i];

  int i=l;
  int j=mid+1;
  for (int k=l; k<=r; k++) {
    if (i>mid) {
        arr[k] = aux[j-l];
        j++;
    } else if (j>r) {
        arr[k] = aux[i-l];
        i++;
    } else if (aux[i-l] > aux[j-l]) {
        arr[k] = aux[i-l];
        i++;
    } else {
        arr[k] = aux[j-l];
        j++;
    }
  }
}

void __mergeSort(int arr[], int l, int r) {
  if (l>=r) return;

  int mid = (l+r)/2;
  __mergeSort(arr, l, mid);
  __mergeSort(arr, mid+1, r);
  merge(arr, l, mid, r);
}

void mergeSort(int arr[], int n) {
  __mergeSort(arr, 0, n-1);
}

归并排序的核心是分治的思想，将大数组分解为小数组处理，算法复杂度为$O(NlogN)$。可以看到以上实现中每次merge时都会创建一个临时局部变量数组，这对于程序性能具有较大的影响，可以在程序开始一次性分配大小为N的辅助空间。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

void merge(int arr[], int aux, int l, int mid, int r) {
  for (int i=l; i<=r; i++) aux[i] = arr[i];

  int i=l;
  int j=mid+1;
  for (int k=l; k<=r; k++) {
    if (i>mid) {
        arr[k] = aux[j];
        j++;
    } else if (j>r) {
        arr[k] = aux[i];
        i++;
    } else if (aux[i] > aux[j]) {
        arr[k] = aux[i];
        i++;
    } else {
        arr[k] = aux[j];
        j++;
    }
  }
}

void __mergeSort(int arr[], int aux[], int l, int r) {
  if (l>=r) return; //此外在元素数量较少时可以使用插入排序来优化程序性能。

  int mid = (l+r)/2;
  __mergeSort(arr, aux, l, mid);
  __mergeSort(arr, aux, mid+1, r);
  merge(arr, aux, l, mid, r); //当arr[mid] <= arr[mid+1]时不需要merge，避免对已经有序的数组归并。对于有序数组时间复杂度为N
}

void mergeSort(int arr[], int n) {
  int aux[n];
  __mergeSort(arr, aux, 0, n-1);
}

快速排序

快速排序算法是一种原地排序且算法复杂度为$O(NlogN)$，而且实现较为简单因而被广泛应用。快速排序的基本思想也是分治，但是与归并算法不同。归并算法是将数组分成两个子数组分别排序并将有序的子数组归并以使整个数组有序，而快速排序则是当两个子数组有序时整个数组自然就有序了。前者递归调用发生在处理整个数组之前，后者发生在之后。此外归并排序中数组被等分为两半而快速排序切分的位置取决于整个数组的内容。快速排序的实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

int partition(int arr[], int l, int r) {
  int v = arr[l];

//定义arr[l+1 ... j] < v, arr[j+1 ... i) > v
  int j=l;
  for (int i=l+1; i<=r; i++) {
    if (arr[i] < v) {
      swap(arr[j+1], arr[i]);
      j++;
    }
  }
  swap(arr[j], arr[l]);
  return j;
}

void __quickSort(int arr[], int l, int r) {
  if (l>=r) return;
  int j=partition(arr, l, r);

  __quickSort(arr, l, j-1);
  __quickSort(arr, j+1, r);
}

void quickSort(int arr[], int n) {
  __quickSort(arr, 0, n-1);
}

当递归的数组长度较小时可以切换为插入排序以提升性能，但是当数组本身为有序数组时每次所选择的主元都位于数组的头部而不能将数组切分，则快速排序的时间复杂度变为$O(NlogN)$。因此可以通过以下方法改进：
1.在开始排序时将数组随机打乱；
2.随机从数组内选择元素当作主元；
3.从数组头部、尾部、中点选择三个元素，取其中的中数作主元；
此外当数组中包含大量重复元素时，以上程序将会把众多相等元素划分到数组的一边，导致数组划分极不平衡从而增大了算法的时间复杂度。因此根据以上分析算法可做以下改进：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

int partition(int arr[], int l, int r) {
  swap(arr[l], arr[l+rand()%(r-l+1)]); //随机选择元素作为主元
  int v = arr[l];

//定义arr[l+1 ... i) <= v, arr(j ... r] >= v
  int i = l+1;
  int j = r;
  while (true) {
    //相等元素也要参与相互交换
    while (i<=r && arr[i] < v) i++;
    while (j>=l+1 && arr[j] > v) j--;
    if (i>=j) break;
    swap(arr[i], arr[j]);
    i++;
    j--;
  }
  swap(arr[j], arr[l]);
  return j;
}

void __quickSort(int arr[], int l, int r) {
  if ( r-l < 20) { //元素个数小于20时切换到插入排序
    insertSort(arr, l, r);
    return;
  }
  int j=partition(arr, l, r);

  __quickSort(arr, l, j-1);
  __quickSort(arr, j+1, r);
}

void quickSort(int arr[], int n) {
  __quickSort(arr, 0, n-1);
}

对于包含有大量重复元素的数组还可以通过将原数组切分成三个子数组，分别为小于、等于和大于主元的情况，而在之后的迭代中只对小于和大于的子数组递归操作。这种三路快速排序在应对大量重复元素情况时效率更好。实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

void __quickSort(int arr[], int l, int r) {
  if ( r-l < 20) { //元素个数小于20时切换到插入排序
    insertSort(arr, l, r);
    return;
  }

  //partition
  v = arr[l];
  int lt = l; //arr[l+1 ... lt] < v
  int gr = r+1; //arr[gt ... r] > v
  int i = l+1; //arr[lt+1 ... i) == v
  while (i<gt) {
    if (arr[i] < v) {
      swap(arr[i], arr[lt+1]);
      lt++;
      i++;
    } else if (arr[i] > v) {
      swap(arr[i], arr[gt-1]);
      gt--;
      i++;
    } else {
      i++;
    }
  }
  swap(arr[l], arr[lt]);
  __quickSort(arr, l, lt-1);
  __quickSort(arr, gt, r);
}

void quickSort(int arr[], int n) {
  __quickSort(arr, 0, n-1);
}