8大经典排序算法
原文发表在我的博客 8大经典排序算法｜以太空间
欢迎访问我的博客 以太空间 | 陈文岗的博客
一、冒泡排序
冒泡排序是一种简单的排序算法。它重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作就是重复地进行直到不需要再进行交换为止，也就是说该数列已经排序完成。这个算法的名字由来就是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
1. 算法描述
比较相邻的元素，如果第一个比第二个大，就交换它们两个；
对每一对相邻的元素作同样的工作，从开始第一队到尾部的最后一对，这样在最后的元素应该会是最大的数；
针对所有的元素重复以上的步骤，直到排序完成
2. 算法排序流程
bubblesort
3. 算法实现
void BubbleSort(int *arr, int n)
{
int i = 0;
int j = 0;
if (arr == NULL)
return;
for (i = 0; i < n - 1; i++)
{
for (j = 0; j < n - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
4. 算法分析
- 最佳情况：O(n)
- 最差情况：O(n^2)
- 平均时间复杂度：O(n^2)
- 空间复杂度为O(1)
- 稳定排序算法
二、选择排序
选择排序是一种简单直观的排序算法。它的工作原理：首先在末排序列中找到最小（大）的元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）的元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
1. 算法描述
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：
- 初始状态：无序区为R[1...n]，有序区为空；
- 第i趟排序(i=1,2,3...n-1)开始时，当前有序区和无序区分别为R[1...i-1]和R[i...n]。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R交换，使R[1...i]和R[i+1...n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；n-1趟结束，数组有序化。
2. 算法排序流程
selectionsort
3. 算法实现
void SelectionSort(int *arr, int n)
{
int i = 0;
int j = 0;
if (arr == NULL)
return;
for (i = 0; i < n; i++)
{
int minIndex = i;
for (j = i; j < n; j++)
{
if (arr[j] < arr[minIndex])
{
minIndex = j;
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
4. 算法分析
- 最佳情况：O(n^2)
- 最差情况：O(n^2)
- 平均时间复杂度：O(n^2)
- 空间复杂度：O(1)
- 不稳定排序算法
三、插入排序
插入排序算法是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描的过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
1. 算法描述
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一个位置；
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤2-5
2. 算法排序流程
insertionsort
3. 算法实现
void InsertionSort(int *arr, int n)
{
int i = 0;
int j = 0;
if (arr == NULL)
return;
for (i = 0; i < n - 1; i++)
{
int currnet = arr[i + 1];
int preIndex = i;
while (preIndex >= 0 && currnet < arr[preIndex])
{
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = currnet;
}
}
4. 算法分析
- 最佳情况：O(n)
- 最坏情况：O(n^2)
- 平均时间复杂度：O(n^2)
- 空间复杂度：O(1)
- 稳定排序算法
四、希尔排序
希尔排序是希尔于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n^2)的第一批算法之一。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
希尔排序是把记录按一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组所包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
1. 算法描述
在此我们选择希尔排序增量为gap = length / 2，缩小增量继续以gap = gap / 2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2,...,1},称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
- 选择一个增量序列t1, t2, ..., tk,其中ti > tj, tk = 1;
- 按增量序列个数k，对序列进行k趟排序；
- 每趟排序，根据对应的增量ti，将待排序序列分隔成若干长度为m的子序列，分别对各子序列进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，子序列长度即为整个序列的长度。
2. 算法排序流程
shellsort
3. 算法实现
void ShellSort(int *arr, int n)
{
int i = 0;
int j = 0;
int temp, gap = n / 2;
if (arr == NULL)
return;
while (gap > 0)
{
for (int i = gap; i < len; i++)
{
temp = arr[i];
int preIndex = i - gap;
while (preIndex >= 0 && arr[preIndex] > temp)
{
arr[preIndex + gap] = arr[preIndex];
preIndex -= gap;
}
arr[preIndex + gap] = temp;
}
gap /= 2;
}
}
4. 算法分析
- 最佳情况：O(nlogn)
- 最坏情况：O(nlogn)
- 平均时间复杂度：O(nlogn)
- 空间复杂度：O(1)
- 不稳定排序算法
五、归并排序
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn)的时间复杂度。代价是需要额外的内存空间。
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使得每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
1. 算法描述
- 把长度为n的输入序列分为两个长度为n/2的子序列；
- 对这两个子序列分别采用归并排序；
- 将两个排序好的子序列合并成一个最终的排序序列。
2. 算法排序流程
mergesort
3. 算法实现
void MergeSort(int a[], int left, int right)
{
int i;
if (left < right)
{
i = (left + right) / 2;
mergeSort(a, left, i);
mergeSort(a, i + 1, right);
merge(a, left, right);
}
}
void merge(int a[], int left, int right)
{
int begin1 = left;
int mid = (left + right) / 2;
int begin2 = mid + 1;
int k = 0;
int newArrayLen = right - left + 1;
int *b = (int *)malloc(newArrayLen * sizeof(int));
while (begin1 <= mid && begin2 <= right)
{
if (a[begin1] <= a[begin2])
b[k++] = a[begin1++];
else
b[k++] = a[begin2++];
}
while (begin1 <= mid)
b[k++] = a[begin1++];
while (begin2 <= right)
b[k++] = a[begin2++];
copyArray(b, a, newArrayLen, left);
free(b);
}
void copyArray(int source[], int dest[], int len, int first)
{
int i;
int j = first;
for (i = 0; i < len; i++)
{
dest[j] = source[i];
j++;
}
}
4. 算法分析
- 最佳情况：O(n)
- 最坏情况：O(nlogn)
- 平均时间复杂度：O(nlogn)
- 空间复杂度：O(n)
- 稳定排序算法
六、快速排序
快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
1. 算法描述
快速排序适用分治法来把一个串分为两个子串。具体算法描述如下：
- 数列中跳出一个元素，称为“基准”
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区操作；
- 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
2. 算法排序流程
quicksort
3. 算法实现
void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
return;
}
void quicksort(int arr[], int maxlen, int begin, int end)
{
int i, j;
if (begin < end)
{
i = begin + 1;
j = end;
while (i < j)
{
if (arr[i] > arr[j])
{
swap(&arr[i], &arr[j]);
j--;
}
else
{
i++;
}
}
if (arr[i] >= arr[j])
{
i--;
}
swap(&arr[i], &arr[j]);
quicksort(arr, maxlen, begin, i);
quicksort(arr, maxlen, j, end);
}
}
4. 算法分析
- 最佳情况：O(nlogn)
- 最坏情况：O(n^2)
- 平均时间复杂度：O(nlogn)
- 空间复杂度：O(nlogn)
- 不稳定排序算法
七、堆排序
堆排序是指利用堆这种数据结构所涉及的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足下面的性质：子结点的键值或索引总是小于（或者大于）它的父结点。
1. 算法描述
- 将初始待排序关键字序列(R1,R2,...,Rn)构建成大（小）根堆，此堆为初始的无序区；
- 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,...,Rn)和新的有序区(Rn)，且满足R[1,2...,n-1]<=R[n];
- 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,...,Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2,...,Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。
2. 算法排序流程
heapsort
3. 算法实现
void HeadAdjust(int arr[], int i, int length)
{
int child;
int temp;
for (; 2 * i + 1 < length; i = child)
{
child = 2 * i + 1;
if (child < length - 1 && arr[child + 1] > arr[child])
child++;
if (arr[i] < arr[child])
{
temp = arr[i];
arr[i] = arr[child];
arr[child] = temp;
}
else
break;
}
}
void HeapSort(int arr[], int length)
{
int i;
for (i = length / 2; i >= 0; --i)
HeadAdjust(arr, i, length);
for (i = length - 1; i > 0; --i)
{
arr[i] = arr[0] ^ arr[i];
arr[0] = arr[0] ^ arr[i];
arr[i] = arr[0] ^ arr[i];
HeadAdjust(arr, 0, i);
}
}
4. 算法分析
- 最佳情况：O(nlogn)
- 最坏情况：O(nlogn)
- 平均时间复杂度：O(nlogn)
- 空间复杂度：O(1)
- 不稳定排序算法
八、基数排序
基数排序是一种非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为O(kn),n为数组长度，k为数组中的数的最大位数；基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级的高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。
1. 算法描述
- 取得数组中的最大数，并取得位数
- arr为原始数组，从最低位开始取每个位组成radix数组；
- 对radix进行计数排序
2. 算法排序流程
radixsort
3. 算法实现
int GetNumIsPos(int num, int pos)
{
int temp = 1;
for (int i = 0; i < pos - 1; i++)
{
temp *= 10;
}
return (num / temp) % 10;
}
void RadixSort(int *pDataArray, int iDataNum)
{
int *radixArrays[10];
for (int i = 0; i < 10; i++)
{
radixArrays[i] = (int *)malloc(sizeof(int) * (iDataNum - 1));
radixArrays[i][0] = 0;
}
for (int pos = 1; pos <= 10; pos++)
{
for (int i = 0; i < iDataNum; i++)
{
int num = GetNumIsPos(pDataArray[i], pos);
int index = ++radixArrays[num][0];
radixArrays[num][index] = pDataArray[i];
}
for (int i = 0, j = 0; i < 10; i++)
{
for (int k = 1; k <= radixArrays[i][0]; k++)
pDataArray[j++] = radixArrays[i][k];
radixArrays[i][0] = 0;
}
}
}
4. 算法分析
- 最佳情况：O(n*k)
- 最坏情况：O(n*k)
- 平均时间复杂度：O(n*k)
- 空间复杂度：O(n)
- 稳定排序算法
总结
sort-summary
