十大经典排序算法汇总总结

zhyjc6于2020-03-30发布 约9042字·约20分钟 本文总阅读量次

前言

名词解释

  • n：数据规模。
  • In-place：也叫原地排序。占用常数内存，不占用额外内存，只利用原来存储待排数据的存储空间进行比较和交换。

  • Out-place：也叫非原地排序。占用额外内存，需要利用额外的数组来辅助排序。

  • 稳定：如果 a 原本在 b 前面 且 a = b，排序之后 a 仍然在 b 的前面。
  • 不稳定：如果 a 原本在 b 的前面 且 a = b，排序之后 a 可能会出现在 b 的后面。
  • 时间复杂度：对排序数据的总的操作次数。反映当 n 变化时，操作次数呈现什么规律。
  • 空间复杂度：是指算法在计算机内执行时所需存储空间的度量。

经典排序算法汇总比较

排序算法分类

按数据量

按稳定性

按时间复杂度

按排序方式

冒泡排序

冒泡排序是最简单的排序算法之一了，对于当前未排序的n个元素，从左到右依次遍历比较相邻的元素，如果左边元素大于右边元素，则交换两个元素。很显然这样一轮下来，我们最终可以确定第n个元素已经是当前n个元素中的最大值了。下一轮是处理前面的n-1个元素。这样一轮确定一个最大元素，n-1轮下来就把所有元素都能确定了。

代码实现

void bubbleSort(vector<int> &arr) {
    if (arr.empty()) return;
	int n = arr.size();
	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], arr[j+1]);
			}
		}
	}
}

改进思路

改进思路1：设置标志位，明显如果有一趟没有发生交换（flag = false)，说明排序已经完成

改进思路2：记录一轮下来交换的最后位置，下次从头部遍历到这个位置就Ok了

选择排序

上面的冒泡排序其实每次遍历的目的就是找到一个当前未排序元素中的最大值，但是其使用的方法是比较每一对相邻的元素，显得十分笨拙。其实我们可以直接遍历一遍找到最大值，然后再将其交换到当前未排序的末尾。这就是选择排序的思想。

选择排序其实可以看做是冒泡排序的优化，每次只用一次交换便得到一个当前的最大值（最小值）。一般来说，选择排序的有序化是从前往后（从左到右），而冒泡排序的有序化是从后往前（从右到左）。即选择排序每次都找到当前未排序元素中的最小值，将其与当前未排序的最左边元素交换，如此进行n-1轮。

代码实现

void selectSort(vector<int> &arr) {
    int n = arr.size();
    for (int i = 0; i < n-1; i++) {
        int minIndex = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            swap(arr[minIndex], arr[i]);
        }
    }
}

为什么不稳定？

如果当前找到的最小元素位于两个相等元素的后面，而该最小元素需要与两个相等元素中的前者交换，那么就破坏了原来那两个相等元素的相对次序，即破坏了稳定性。
如：5 8 5 2 9
第一轮是交换后就变成：
2 8 5 5 9

插入排序

插入排序不用像冒泡排序和选择排序那样要交换两个元素，插入排序的思想在于：找到位置->移动元素来腾出位置->插入元素。但是一般的实现是在找位置的过程中就移动元素，等到找到位置的时候，位置的空间已经被空出来了，只需要插入元素即可。

代码实现

void insertSort(vector<int> &arr){
    if (arr.empty()) return;
    for (int i = 1; i < arr.size(); i++) {
        int temp = arr[i];
        int j = i;
        while (j > 0 && temp < arr[j-1]){
            arr[j] = arr[j-1];
            j--;
        }   
        arr[j] = temp;
    }   
}

希尔排序

正如选择排序是冒泡排序的优化，希尔排序则是插入排序的优化。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为普通插入排序，这就保证了数据一定会被排序。

希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比$O(n^2)$好一些。

代码实现

void shellSort(vector<int> &arr) {
    if (arr.empty()) return;
    int n = arr.size();
    for (int gap = n/2; gap > 0; gap >>= 1) {
        for (int i = gap; i < n; i++) {//插入排序
            int temp = arr[i];
            int j = i;
            while (j-gap >= 0 && temp < arr[j-gap]) {
                arr[j] = arr[j-gap];
                j -= gap;
            }
            arr[j] = temp;
        }   
    }   

}

为什么不稳定？

希尔排序是几次插入排序的组合。一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
例如待排序列为：2 2 1 3 4，选择步长依次为：2 1
那么首先进行步长为2的插入排序：
	  2 2 1 3 4
第一组:2   1   4
第二组： 2   3

第一轮排序后：
第一组:1   2   4
第二组:  2   3
	  1 2 2 3 4（此时两个2已经错位，因此不稳定）

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列。若将两个有序表合并成一个有序表，称为2-路归并。

代码实现

void merge(vector<int> &arr, int left, int mid, int right) {
    vector<int> temp(right-left+1);
    int i = left, j = mid+1, k = 0;
    while (i <= mid && j <= right) {
        if (arr[i] < arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    for (int idx = 0; idx < temp.size(); idx++) {
        arr[left+idx] = temp[idx];
    }
}
void mergesort(vector<int> &arr, int left, int right) {
    if (left >= right) return;
    int mid = left + (right-left)/2;
    mergesort(arr, left, mid);
    mergesort(arr, mid+1, right);
    merge(arr, left, mid, right);
}
void mergeSort(vector<int> &arr) {
	if (arr.empty()) return;
    mergesort(arr, 0, arr.size()-1);
}

快速排序

快速排序是实际应用中使用使用最多性能最好的排序算法，但其思想却与普通的冒泡排序有关。冒泡排序是一一比较和交换相邻元素将最大值移动到最右端。而快速排序则是设定一个中轴元素，不断交换大于等于该中轴元素的元素和小于该中轴元素的元素，这样一来只要一次交换就能把一个大元素移动到右端，一个小元素移动到左端。再配合分治策略以及递归，才成就了现在的快排。

我们从数组中选择一个元素，我们可以形象地把这个元素称之为中轴元素，然后把数组中所有小于中轴元素的元素放在其左边，所有大于或等于中轴元素的元素放在其右边，显然，此时中轴元素所处的位置的是有序的。也就是说，我们无需再移动中轴元素的位置。递归地进行以上操作。

代码实现1：递归

int partition(vector<int> &arr, int left, int right) {
    int pivot = left;
    int less = left + 1;
    for (int i = left+1; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr[less++], arr[i]);
        }
    }
    swap(arr[--less], arr[pivot]);
    return less;
}
void quicksort(vector<int> &arr, int left, int right) {
    if (left >= right) return;
    int mid = partition(arr, left, right);
    quicksort(arr, left, mid-1);
    quicksort(arr, mid+1, right);
}
void quickSort(vector<int> &arr) {
    if (arr.empty()) return;
    quicksort(arr, 0, arr.size()-1);
}

代码实现2：迭代

void quickSort(vector<int>& arr) {
	if (arr.empty()) return;
	stack<pair<int, int>> stack;
	int l = 0, r = arr.size() - 1;
	stack.push({ l, r });
	while (!stack.empty()) {
		auto lr = stack.top(); stack.pop();
		l = lr.first;
		r = lr.second;
		int pivot = arr[l];
		int idx = l + 1;
		for (int i = l + 1; i <= r; ++i) {
			if (arr[i] < pivot) {
				swap(arr[idx++], arr[i]);
			}
		}
		swap(arr[l], arr[--idx]);
		if (l < idx - 1) {
			stack.push({ l, idx - 1 });
		}
		if (idx + 1 < r) {
			stack.push({ idx + 1, r });
		}
	}
}

为什么不稳定？

快速排序是不稳定的排序算法。这是因为快速排序使用了交换的方式 将 元素分为大于等于基准元素的元素和小于基准元素的元素两部分，例如

p | lower | higher | unvisited
p指的是pivotal，lower指小于p的部分，unvisited指还未访问到，| 是分割线。

5 | 3 1 2 | 9 7 8 9 | 4 6 3
此时正准备遍历4

5 | 3 1 2 4 | 7 8 9 9 | 6 3
4与第1个9交换，因此两个9就错位了

堆排序

在给出的待排序数组中直接构造堆（升序用大顶堆），由于大顶堆的堆顶总是当前堆的最大值，因此每次将堆顶与堆中最后元素互换，并从堆中取下原堆顶元素，然后再调整堆为新的大顶堆。直到堆中只有一个元素，那么其一定是最小值，且一定是在数组首部。

堆排序有点类似于冒泡排序和选择排序，每次都确定一个未排序元素中的最大值，将其取出按顺序依次放在已排序序列中。不同的是堆排序使用大顶堆来找最大值，因此可以直接取得。堆排序的核心是如何维护堆始终是一个大顶堆。

代码实现

void sink(vector<int> &arr, int root, int end) { //当前结点小于某个子结点，将其下沉
    int maxIdx = root;
    int left = 2 * root + 1, right = 2 * root + 2;
    if (left <= end && arr[left] > arr[maxIdx]) {
        maxIdx = left;
    }   
    if (right <= end && arr[right] > arr[maxIdx]) {
        maxIdx = right;
    }   
    if (maxIdx != root) {
        swap(arr[root], arr[maxIdx]);
        sink(arr, maxIdx, end);
    }   
}
void heapSort(vector<int> &arr) {
    if (arr.empty()) return;
    int n = arr.size();
    for (int i = n/2-1; i >= 0; --i) { //建堆是前提
        sink(arr, i, n-1);
    }   
    for (int i = n-1; i > 0; --i) {
        swap(arr[0], arr[i]);
        sink(arr, 0, i-1);
    }   
}

为什么不稳定？

堆排序如同选择排序，每次确定一个最大值（只不过堆排序的最大值是直接从堆顶取的），然后将其放到数组末尾。如果原数组中两个相等的元素，前者先成为堆顶，那么前者就先进入有序序列，最终将导致两个相等元素的错位。
个人总结主要分两种情况：
	一种是大顶堆构建好前堆顶已经是最大元素且还有等于堆顶元素的元素，此时引起算法不稳定的因素是堆顶和堆尾元素交换，然后再断尾；
	另一种情况是堆中根结点与两个子结点比较大小的时候，常常会先和左子结点比较（大部分情况下是这样引起不稳定的），然后再与右子结点比较。如果左右两个结点相等且都比根结点大，那么左结点会更新为新的根结点，从而先脱离堆，先进入原数组尾部有序部分，从而与原来的又子结点错位。（这点可以避免，但情况一无法避免）
	
情况一：6a 5 6b  ->  5 6b 6a
   6a     排序      6b      排序       5
  /  \     ->     /         ->       
 5    6b         5    6a           6b   6a
	
	
情况二：5 6a 6b    ->   5 6b 6a (两个6错位了)
    5      建堆      6a      排序    6b      排序    5
   / \      ->     /  \      ->    /         ->    
 6a   6b          5    6b         5    6a       6b   6a

计数排序

计数排序顾名思义就是需要计数，计算数量。具体实现是使用一个计数数组来存储待排序元素中每个元素出现的次数。由于计数数组中包含原数组的信息，因此我们可以直接使用计数数组的信息覆盖待排序数组。

代码实现

void countSort(vector<int> &arr) {
    if (arr.empty()) return;
    int max_v = arr[0];
    int min_v = arr[0];
    for (int num : arr) { //求数组中元素的取值范围
        max_v = max(max_v, num);
        min_v = min(min_v, num);
    }   
    vector<int> count(max_v - min_v + 1, 0); 
    for (int num : arr) {
        count[num-min_v]++; //将对应的元素映射到对应的数组索引
    }   
    int k = 0;
    for (int i = 0; i < (int)count.size(); ++i) {
        int num = i + min_v; //从数组索引还原元素
        for (int j = 0; j < count[i]; ++j) { //元素次数
            arr[k++] = num;
        }
    }   
}

基数排序

基数排序（Radix Sort）是多关键字排序，即基数排序可以排序多元组。例如成绩排序，首先按语文成绩排序，然后按数学成绩排序，这样就可以对多元组（语文成绩，数学成绩）排序了。其实数的排序也可以是多元组排序，每个数（十进制）的个位、十位、千位……，每一个位就是一个关键字，每一个位上的数字对数的大小影响力不同。如果我们先根据权重最小的关键字排序，最后再根据权重最大的关键字排序，那么我们称之为LSD(Least Significant Digital)排序，反之则称为MSD(Most Significant Digital)排序。一般情况下我们使用LSD排序。

LSD排序模式必须使用稳定排序用于辅助，MSD则不要求。

例如：

如果不使用稳定排序，那么
[12, 23, 14] 排序后就可能变为 [14, 12, 23]

代码实现（LSD）

void countsort(vector<int> &arr, int radix) {
      vector<int> tmp(arr.size());
      vector<int> count(10, 0); 
      for (int num : arr) {
          count[(num / radix) % 10]++; //计数
      }   
      for (int i = 1; i < (int)count.size(); ++i) {
          count[i] += count[i-1]; //累加
      }   
      for (int i = arr.size()-1; i >= 0; --i) {
          int idx = (arr[i] / radix) % 10; 
          tmp[--count[idx]] = arr[i]; //将相应元素放到对应位置
      }   
      for (int i = 0; i < (int)arr.size(); ++i) {
          arr[i] = tmp[i]; //将已排序数组复制到原数组
      }   
  }
  void radixSort(vector<int> &arr) {
      if (arr.empty()) return;
      int max_v = arr[0]; //找到最大值
      for (int num : arr) max_v = max(max_v, num);
      for (int radix = 1; radix <= max_v; radix *= 10) { //最大值的位数次循环
          countsort(arr, radix); //以当前位为基准借用计数排序进行排序，计数排序是稳定排序
      }
  }

桶排序

之所以把桶排序放在三种线性排序中的最后，是因为桶排序与前面两种线性排序有着某种关联。我自己的感受是：桶排序是基础，而计数排序和基数排序都是桶排序衍生出来的特例。例如，把桶排序中桶的大小设置为1，即变成了计数排序。把桶的数量设置为10，那么就变成了一轮基数排序。但基数排序要比计数排序和桶排序都高一个维度，因为它可以处理多关键字的排序。

代码实现

void bucketSort(vector<int> &arr) {
    if (arr.empty()) return;
    int min_ = arr[0], max_ = arr[0];
    for (int &num : arr) {
        min_ = min(min_, num);
        max_ = max(max_, num);
    }
    const int count_of_bucket = min(10, max_ - min_ + 1);
    const int size_of_bucket = (max_ - min_ + 1) / count_of_bucket + 1;
    vector<vector<int>> bucket(count_of_bucket);

    for (int &num : arr) {
        int whichone = (num - min_) / size_of_bucket;
        bucket[whichone].push_back(num);
    }
    int k = 0;//回填原数组
    for (int i = 0; i < count_of_bucket; i++) {
        sort(bucket[i].begin(), bucket[i].end());
        for (auto &num : bucket[i]) {
            arr[k++] = num;
        }
    }
}

参考资料