一、排序概念
排序：对一序列对象根据某个关键字进行排序。
稳定：如果 a 原本在 b 前面，而 a 与 b 的值相等，排序之后 a 仍然在 b 的前面；
不稳定：如果 a 原本在 b 的前面，而 a 与 b 的值相等，排序之后 a 可能会出现在b的后面；内排序：所有排序操作都在内存中完成；
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；排序耗时的操作：比较、移动；
-
排序分类：
- 交换类：冒泡排序、快速排序；此类的特点是通过不断的
比较和交换进行排序； - 插入类：简单插入排序、希尔排序；此类的特点是通过
插入的手段进行排序； - 选择类：简单选择排序、堆排序；此类的特点是
看准了再移动； - 归并类：归并排序；此类的特点是
先分割后合并；
- 交换类：冒泡排序、快速排序；此类的特点是通过不断的
历史进程：一开始排序算法的复杂度都是在
O(n^2)，希尔排序的出现打破了这个僵局。
二、排序算法
最简单的排序算法
最简单的排序实现，缺点是每次找最小值都是单纯的找，而没有为下一次寻找做出铺垫；
C 代码
//最简单的排序, arr表示数组首地址，count表示数组的元素个数
void simpleSort(int *arr, int count)
{
for (int i = 0; i < count; i++) {
for (int j = i+1; j < count; j++) {
if (arr[i] > arr[j]) {
swap(arr+i, arr+j);
}
}
}
}
Swift 代码
func simpleSort(_ arr: [Int]) -> [Int] {
var sortArr = arr;
for i in 0..<sortArr.count {
for j in (i+1)..<sortArr.count {
if sortArr[i] > sortArr[j] {
swap(&sortArr[i], &sortArr[j]);
}
}
}
return sortArr;
}
1. 冒泡排序
- 冒泡排序相对于最简单的排序有了改进，即每次交换都是对后续有帮助的，大数将会越来越大，小的数将会越来越小；
- 思想：两两相邻元素之间的比较，如果前者大于后者，则交换；
C 代码
//arr表示数组的首地址，count表示数组元素的个数
void bubbleSort(int *arr, int count)
{
for (int i = 0; i < count; i++) {
for (int j = 0; j < count - i - 1; j++) {
if (arr[j] > arr[j+1]) {
swap(arr+j, arr+j+1);
}
}
}
}
Swift 代码
func bubbleSort(_ arr: [Int]) -> [Int] {
var sortArray = arr;
//循环按照从后往前的顺序确定位置，依次确定最后一个位置、倒数第二个位置...
for i in 0..<sortArray.count {
for j in 0..<(sortArray.count-i-1) {
if sortArray[j] > sortArray[j+1] {
swap(&sortArray[j], &sortArray[j+1]);
}
}
}
return sortArray;
}
改进冒泡排序
- 如果出现一个序列，此序列基本是有序的，如果是标准的冒泡排序，则还是需要进行不断的比较；
- 改进方法：通过填加一个
boolean类型的变量，如果一次循环中没有交换过元素，则说明已经排好序。
C 代码
//最好：n-1次比较，不移动。因此时间复杂度为O(n)，不占用辅助空间。
//最坏：n(n-1)/2次比较和移动，因此为O(n^2)，占用交换的临时空间，大小为1；
void bubbleSort1(int *arr, int count)
{
bool isChanged = true;
for (int i = 0; i < count && isChanged; i++) {
isChanged = false;
for (int j = 0; j < count - i - 1; j++) {
if (arr[j] > arr[j+1]) {
swap(arr+j, arr+j+1);
isChanged = true;
}
}
}
}
Swift 代码
//改进冒泡排序
//最好：n-1次比较，不移动位置。时间复杂度为O(n)，不占用辅助空间。
//最坏：n(n-1)/2次比较和移动，因此O(n^2)，占用交换的临时空间，大小为1。
func bubbleSort2(_ arr: [Int]) -> [Int] {
var sortArray = arr;
var isChanged = true;
for i in 0..<sortArray.count {
if !isChanged {
break;
}
isChanged = false;
for j in (i..<sortArray.count-1).reversed() {
if sortArray[j] > sortArray[j+1] {
swap(&sortArray[j], &sortArray[j+1]);
isChanged = true;
}
}
}
return sortArray;
}
2. 简单选择排序
- 特点：每次循环找到最小值，并交换。因此交换次数始终为n-1次。
- 相对于最简单的排序，对不必要的交换做了改进，每个循环不断比较后记录最小值，只做了一次交换。（也可能不交换，当最小值已经在正确的位置）
C 代码
void selectSort(int *arr, int count)
{
for (int i = 0; i < count; i++) {
int min = i;
for (int j = i+1; j < count; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}
if (min != i) {
swap(arr+i, arr+min);
}
}
}
Swift 代码
//最差：n(n-1)/2次比较，n-1次交换，因此时间复杂度为O(n^2)
//最好：n(n-1)/2次比较，不交换，因此时间复杂度为O(n^2)
//好于冒泡排序
func selectSort(_ arr: [Int]) -> [Int] {
var sortArray = arr;
for i in 0..<sortArray.count {
var min = i;
for j in i+1..<sortArray.count {
if sortArray[min] > sortArray[j] {
min = j;
}
}
if min != i {
swap(&sortArray[min], &sortArray[i]);
}
}
return sortArray;
}
3. 简单插入排序
- 思想：给定序列，存在一个分界线，分界线的左边被认为是有序的，分界线的右边还没被排序。每次取没被排序的最左边一个和已排序的做比较，并插入到正确位置；我们默认索引 0 的子数组有序；每次循环将分界线右边的一个元素插入到有序数组中，并将分界线向右移一位；
C 代码
void insertSort(int *arr, int count)
{
int j;
for (int i = 1; i < count; i++) {
int temp = arr[i];
for (j = i; j > 0 && temp < arr[j-1]; j--) {
arr[j] = arr[j-1];
}
//注意要插入的位置
arr[j] = temp;
}
}
Swift 代码
//最好：n-1次比较，0次移动，时间复杂度为O(n)
//最差：n(n-1)/2次比较，n(n-1)/2次移动，时间复杂度为O(n^2)
func insertSort(_ arr: [Int]) -> [Int] {
var sortArray = arr;
for i in 1..<sortArray.count {
if sortArray[i] < sortArray[i-1] {
let temp = sortArray[i];
var index = i;
for j in (0..<i).reversed() {
if sortArray[j] > temp {
//如果没找到位置，继续寻找
sortArray[j+1] = sortArray[j];
//记录位置
index = j;
continue;
}
}
//找到位置, 插入数值
sortArray[index] = temp;
}
}
return sortArray;
}
4. 希尔排序
- 希尔排序是第一个突破O(n^2)的排序算法，是简单插入排序的改进版；
- 思想：由于简单插入排序对于记录较少或基本有序时很有效，因此我们可以通过将序列进行分组排序，使得每组容量变小，再进行分组排序，然后进行一次简单插入排序即可；
- 增量的选择十分重要，可以选择length/2这样的方式，也是希尔建议的增量，称为希尔增量。另外，增量最小为1。
C 代码
//希尔排序的步长选择从length/2开始，每次再减半，直到最后为1。其实也可以有另外的更高效的步长选择，不过最后需要保证增量为1。
void shellSort(int *arr, int count)
{
int increment = count;
do {
//设置希尔初始增量为数组长度的一半
increment = increment / 2;
if (increment == 0) {
increment = 1;
}
int j;
for (int i = increment; i < count; i++) {
int temp = arr[i];
//j指向有序区的最后一个元素
for (j = i-increment; j >= 0 && temp < arr[j]; j -= increment) {
arr[j+increment] = arr[j];
}
//找到合适的位置，插入元素
arr[j+increment] = temp;
}
} while (increment > 1);
}
Swift 代码
//希尔排序的步长选择从length/2开始，每次再减半，直到最后为1。其实也可以有另外的更高效的步长选择，不过最后需要保证增量为1。
func shellSort(_ arr: [Int]) -> [Int] {
var sortArray = arr;
var increment = arr.count;
repeat {
//设置希尔初始增量为数组长度的一半
increment = increment / 2;
if increment == 0 {
increment = 1;
}
for i in increment..<sortArray.count {
let temp = sortArray[i];
//j指向有序区的最后一个元素
var j = i - increment;
//循环找到合适的位置插入元素
while j >= 0 && temp < sortArray[j] {
sortArray[j+increment] = sortArray[j];
j -= increment;
}
sortArray[j+increment] = temp;
}
} while increment > 1;
return sortArray;
}
5. 堆排序
- 大根堆：任意父结点都比子结点大；
小根堆：任意父结点都比子结点小； - 堆排序是不稳定的排序算法，是简单选择排序的改进版。
- 堆的存储：一般用数组来表示堆，若根结点存在序号 0 处，i 结点的父结点下标就为 (i-1)/2。i 结点的左、右子结点下标分别为 2*i+1 和 2*i+2。如果根节点是从 1 开始，则左、右子结点分别是 2i 和 2i+1。
- 完全二叉树有 n 个结点，则拥有 n/2 个非叶子结点。（取整）
- 思想：构建一颗完全二叉树。首先构建大根堆，然后每次把根节点（最大值）和最后的节点（最小值）互换，然后将数组长度减一。之后重新构建大根堆，以此类推。
- 注意：此排序方法不适用于个数少的序列，因为初始构建需要时间。
C 代码
//堆排序
void heapSort(int *arr, int count)
{
//1.首先构建大根堆
for (int i = (count-1)/2; i >= 0; i--) {
heapAdjust(arr, i, count);
}
//2.将根结点与尾结点互换，数组长度减去1，重新构建大根堆
for (int i = 1; i < count; i++) {
swap(arr, arr+count-i);
heapAdjust(arr, 0, count-i);
}
}
//调整数组为大根堆，parent表示根节点的下标，count表示要调整的数组长度
void heapAdjust(int *arr, int parent, int count)
{
//保存根结点的数值
int temp = arr[parent];
//获取根节点的左子节点（下标从0开始）
for (int i = parent * 2 + 1; i < count; i = i * 2 + 1) {
//找到左、右子结点的较大者
if (i < count-1 && arr[i] < arr[i+1]) {
i = i + 1;
}
//根结点大于等于左、右子结点
if (temp >= arr[i]) {
break;
}
//将根结点与左、右子结点较大者替换
arr[parent] = arr[i];
//再次检查子结点的子结点
parent = i;
}
arr[parent] = temp;
}
Swift 代码
func heapSort(_ arr: [Int]) -> [Int] {
var sortArray = arr;
let count = sortArray.count;
//首先建立大根堆
//先找到最后一个拥有子结点的根结点
var i = count / 2 - 1;
while i >= 0 {
heapAdjust(&sortArray, parent: i, count: count);
i -= 1;
}
//进行排序
for i in 1..<count {
//将最后一个元素和第一个元素进行交换
swap(&sortArray[0], &sortArray[count-i]);
//数组的长度减一，然后将剩下的无序数组调整为大根堆
//由于只是头结点无序，所以只需要调整头结点即可，其他结点不需要调节
heapAdjust(&sortArray, parent: 0, count: count-i);
}
return sortArray;
}
//调整指定结点以下为大根堆，parent表示父结点的下标，count表示要调整的数组长度
func heapAdjust(_ arr: inout [Int], parent: Int, count: Int) {
//保存根结点的数值
let temp = arr[parent];
var parent = parent;
//获取根结点的左子结点
var i = parent * 2 + 1;
while i < count {
if i < count-1 && arr[i] < arr[i+1] {
//记录左右子结点的较大者
i = i + 1;
}
//如果根节点数大于子结点数，则中止循环，否则沿着一路循环下去
if temp >= arr[i] {
break;
}
//将较大值赋值到根结点
arr[parent] = arr[i];
//更新当前根结点的位置
parent = i;
//寻找parent的左子结点进行下一轮循环
i = i * 2 + 1;
}
arr[parent] = temp;
}
6. 归并排序
- 稳定的排序算法
- 思想：利用递归进行分割和合并，分割直到长度为1为止，并在合并前保证两序列原本各自有序，合并后也有序。
C 代码
//归并排序
void mergeSort(int *arr, int count)
{
for (int gap = 1; gap < count; gap = 2 * gap) {
mergePass(arr, gap, count);
}
}
//gap表示字表的长度，count表示数组的个数
void mergePass(int *arr, int gap, int count)
{
//需要合并的两个序列的计算：
//low = 2 * gap * i;
//mid = low + gap - 1;
//high = low + 2 * gap - 1;
//这里的i就代表low，要合并的第一个序列的最小下标
int i = 0;
for (i = 0; i + 2 * gap - 1 < count; i = i + 2 * gap) {
mergeArray(arr, i, i + gap - 1, i + 2 * gap - 1);
}
//可能有奇数个元素，有则合并剩下的序列
if (i + gap - 1 < count) {
mergeArray(arr, i, i + gap - 1, count - 1);
}
}
//合并数组元素，low表示第一段序列的最小下标，mid表示第一段序列的最大下标，high表示第二段序列的最高下标
void mergeArray(int *arr, int low, int mid, int high)
{
int i = low; //第一段序列的下标
int j = mid + 1; //第二段序列的下标
int k = 0; //k是存放合并序列的下标
int *array = (int *)malloc((high - low + 1) * sizeof(int)); //申请临时空间
//扫描第一段和第二段序列，直到有一个扫描结束
while(i <= mid && j <= high) {
//判断第一段和第二段取出的数哪个更小，将其加入合并序列，并继续向下扫描
if (arr[i] < arr[j]) {
array[k] = arr[i];
i++;
k++;
} else {
array[k] = arr[j];
j++;
k++;
}
}
//若第一段序列还没扫描完，将其全部复制到合并序列
while (i <= mid) {
array[k] = arr[i];
i++;
k++;
}
//若第二段序列还没扫描完，将其全部复制到合并序列
while (j <= high) {
array[k] = arr[j];
j++;
k++;
}
//将合并序列复制到原始序列中
for (k = 0, i = low; i <= high; i++, k++) {
arr[i] = array[k];
}
//释放空间
free(array);
}
Swift 代码
//归并排序
func mergeSort(_ arr: inout [Int]) {
var gap = 1;
while gap < arr.count {
mergePass(&arr, gap: gap);
gap *= 2;
}
}
//分解合并序列
func mergePass(_ arr: inout [Int], gap: Int) {
var i = 0;
let count = arr.count;
while i + 2 * gap - 1 < count {
mergeArray(&arr, low: i, mid: i + gap - 1, high: i + 2 * gap - 1);
i += 2 * gap;
}
//合并剩余的序列
if i + gap - 1 < count {
mergeArray(&arr, low: i, mid: i + gap - 1, high: count - 1);
}
}
//合并两个序列
func mergeArray(_ arr: inout [Int], low: Int, mid: Int, high: Int) {
var i = low;
var j = mid + 1;
var k = 0;
var array = Array<Int>(repeating: 0, count: high - low + 1);
while i <= mid && j <= high {
if arr[i] < arr[j] {
array[k] = arr[i];
i += 1;
k += 1;
} else {
array[k] = arr[j];
j += 1;
k += 1;
}
}
while i <= mid {
array[k] = arr[i];
i += 1;
k += 1;
}
while j <= high {
array[k] = arr[j];
j += 1;
k += 1;
}
//将排序好的序列复制回原数组
k = 0;
for i in low...high {
arr[i] = array[k];
k += 1;
}
}
7. 快速排序
- 冒泡排序的升级版，现在用的最多的排序方法；
- 思想：选取pivot，将pivot调整到一个合理的位置，使左边的值都小于它，右边的值都大于它；
- 注意，如果序列基本有序或者序列个数较少，则可以采用简单插入排序。因为快速排序对这些情况效率不高。
C 代码
//快速排序
void quickSort(int *arr, int low, int high)
{
if (low < high) {
int key = partition(arr, low, high);
//对数组左边进行排序
quickSort(arr, 0, key-1);
//对数组右边 进行排序
quickSort(arr, key+1, high);
}
}
//划分数组，左边的数据都小于piovt，右边的数据都大于piovt
int partition(int *arr, int low, int high)
{
int piovtKey = arr[low]; //这个地方可以优化
while (low < high) {
//遍历右边，直到小于piovtKey
while (low < high && arr[high] >= piovtKey) {
high--;
}
arr[low] = arr[high];
//遍历左边，直到大于piovtKey
while (low < high && arr[low] <= piovtKey) {
low++;
}
arr[high] = arr[low];
}
//将piovtKey赋值到中间位置
arr[low] = piovtKey;
//返回中间位置，low和high都可以，此时low与high相等
return low;
}
Swift 代码
//快速排序
func quickSort(_ arr: inout [Int], low: Int, high: Int) {
if low < high {
let p = partition(&arr, low: low, high: high);
//左边递归排序
quickSort(&arr, low: 0, high: p-1);
//右边递归排序
quickSort(&arr, low: p+1, high: high);
}
}
//将数组分成两部分，左边部分小于pivotKey的值，右边部分大于pivotKey的值
func partition(_ arr: inout [Int], low: Int, high: Int) -> Int {
var low = low;
var high = high;
let pivotKey = arr[low];
while low < high {
//循环右边，直到小于pivotKey
while low < high && arr[high] >= pivotKey {
high -= 1;
}
arr[low] = arr[high];
//循环左边，直到大于pivotKey
while low < high && arr[low] <= pivotKey {
low += 1;
}
arr[high] = arr[low];
}
//将pivotKey放置到中间的位置，返回划分的位置
arr[low] = pivotKey;
return low;
}
快速排序优化方案
- 选取pivot：选取pivot的值对于快速排序至关重要，理想情况，pivot应该是序列的中间数。前面我们只是简单的取第一个数作为pivot，这点可以进行优化。
- 优化方法：抽多个数后取中位数作为pivot。
- 对于小数组使用插入排序：因为快速排序适合大数组排序。如果是小数组，则效果没有简单插入排序效果好。
三、排序总结
- 数组长度不大的情况下不宜使用归并排序，其它排序差别不大。
- 数组长度很大情况下希尔排序最快，快速排序其次，冒泡排序最慢。
总结：每个排序都有各自的特点，我们需要在适当的时候用适当的算法。比如在基本有序、数组规模小的时候用直接插入排序；比如在大数组时用快速排序；比如想要稳定性，则使用归并排序；
| 排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
| 简单选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 直接插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
| 希尔排序 | O(n^1.3) | O(n) | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn) ~ O(n) | 不稳定 |
