常见的排序算法
- 一、冒泡排序(Bubble Sort)
- 二、插入排序(Insert Sort)
- 三、选择排序 (Selection Sort)
- 四、希尔排序(Shell Sort)
- 五、快速排序(Quick Sort)
- 六、堆排序(Heap Sort)
- 七、归并排序(Merge Sort)
- 八、计数排序(Count Sort()
- 九、桶排序 (Bucket Sort)
- 十、基数排序 (Radix Sort)
- 总结
一、冒泡排序(Bubble Sort)
基本思想:遍历所有的数据,每次对相邻元素进行两两比较,如果顺序和预先规定的顺序不一致,则进行位置交换;这样一次遍历会将最大或最小的数据上浮到顶端,之后再重复同样的操作,直到所有的数据有序。
C语言实现
//冒泡排序 ,指的是元素两两之间进行比较交换,需要比较n轮,每轮需要比较m次,从左向右升序
void bubbleSort(int buf[],int bufsize)
{int temp = 0; //为了临时存储交换值//1.循环比较元素,需要比较n轮for (int n = 1; n < bufsize; ++n){//2.每轮需要比较m次for (int m = 0; m < bufsize-n; ++m){//3.数组元素两两之间进行比较交换 buf[0] buf[1] buf[1] buf[2]if (buf[m] > buf[m+1]){temp = buf[m]; //备份前一个buf[m] = buf[m+1];//把后面交换到前面buf[m+1]= temp; //把前面交换到后面}}}
}
二、插入排序(Insert Sort)
直接插入排序是一种简单的插入排序法,其基本思想是:从第二个元素开始,将每个元素插入到已排序的数组中的适当位置,直到整个数组排序完成。
C语言实现
//插入排序 是把无序序列中元素依次插入到有序序列中,一般是从有序序列的尾部开始比较
void InsertSort(int buf[10],int bufsize)
{int temp = 0,i,j; /temp/用于备份当前待插入元素的值//1.可以假设把数组中的第一个元素作为有序序列的元素,剩下的元素作为无序序列for (i = 1; i < bufsize; ++i){//2.先备份当前待插入元素的值temp = buf[i]; //3.把当前待插入元素和有序序列中的元素依次进行比较,从有序序列尾部开始for (j = i-1; j >= 0; j--){if (temp>buf[j])//此时插入元素比该有序元素大break; //找到了待插入位置//此时插入元素比该有序元素小buf[j+1]=buf[j]; //将该有序元素后移一个单位}//4.把待插入元素插入到指定位置buf[j+1] = temp;}
}
三、选择排序 (Selection Sort)
每次从未排序的部分选出最小(或最大)的元素,然后与未排序部分的第一个元素交换位置,如此反复直到整个数组排序完成。
C语言实现
我们可以对此算法进行优化,在每次对未排序的元素进行遍历中同时选出最小和最大的元素,分别放在原序列的序列头和序列尾,这样只需遍历序列的一半次数即可。
void Swap(int* p1, int* p2)
{ //实现数据交换int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;//记录待排序的范围:开头和末尾while (begin < end){int maxi = begin, mini = begin;for (int i = begin; i <= end; i++){if (a[i] > a[maxi]){maxi = i;}if (a[i] < a[mini]){mini = i;}}Swap(&a[mini], &a[begin]);if (maxi == begin)//考虑特殊情况{//当begin和maxi相同的时候,由于a[mini]和a[begin]进行了交换,最大值不在原本的位置,所以要换回来maxi = mini;}Swap(&a[maxi], &a[end]);//此时经过一轮排序,待排序数列的最大,最小值已经找到,范围进行缩小++begin;--end;}
}
四、希尔排序(Shell Sort)
使用不同的步长将数组分成几个子数组,针对每个子数组进行插入排序,然后逐渐减小步长,如此反复直到整个数组排序完成。
例如这组数据是
{8,9,1,7,2,3,5,4,6,0}
首次取gap=5,即视间隔为5的数为一组进行插入排序:
{8 3 }->
{3 8 }
{ 9 5 }->
{ 5 9 }
{ 1 4 }->
{ 1 4 }
{ 7 6 }->
{ 6 7 }
{ 2 0}->
{ 0 2}
即原先的数组变为
{8917235460}->
{3516089472}
当gap=2时,即视间隔为5的数为一组进行插入排序:
{3 1 0 9 7 }->
{0 1 3 7 9 }
{ 5 6 8 4 2}->
{ 2 4 5 6 8}
即
{3516089472}->
{0214357698}
当最后gap=1时,即直接插入排序。
C语言实现
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap /= 2; // gap /= 3 + 1;//gap > 1时都是预排序// gap = 1时就是直接插入排序//把间隔为gap的数据同时排for (int i = 0; i < n - gap; ++i){int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}
五、快速排序(Quick Sort)
以数组中的某个元素为基准(比如中间元素),将数组分成两个子数组,左边的子数组的所有元素都小于基准元素,右边的子数组的所有元素都大于基准元素,然后递归地重复这个过程直到排序完成。
C语言实现
void Swap(int* a,int* b)
{int tmp = *a;*a = *b;*b = tmp;
}
int PartSort(int* arr,int left,int right)
{int keyi = left;while (left < right)//left等于right时退出循环{while (left < right && arr[right] >= arr[keyi])//防止越界加上left < right条件{right--;}while (left < right && arr[left] <= arr[keyi]){left++;}Swap(&arr[left], &arr[right]);}Swap(&arr[keyi], &arr[left]);//此时left与right相同return keyi;
}void QuickSort(int* arr, int begin, int end)//使用时要传下标
{if (begin >= end)return;int keyi = PartSort(arr, begin, end);//[begin,keyi+1] keyi [keyi+1,end]QuickSort(arr, 0, keyi - 1);QuickSort(arr, keyi + 1, end);
}
六、堆排序(Heap Sort)
通过将数组转换为最大堆来排序,然后重复从堆中弹出最大元素并将其放入已排序的数组中的过程,直到整个数组排序完成。
C语言实现
void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;//找到左孩子while (child < n)//判断左孩子是否存在,因为在完全二叉树中,左孩子如果不存在,右孩子一定不存在{//判断右孩子是否存在,如果不存在child默认为左孩子//如果右孩子存在且比左孩子小,child++就表示右孩子了if (child + 1 < n && a[child] > a[child + 1]){child++;}//用较小的孩子与父亲比较if (a[parent] > a[child]){Swap(&a[parent], &a[child]);parent = child;//更新child = parent * 2 + 1;}else{//孩子不存在退出,或无需交换退出break;}}
}void HeapSort(int* a, int n)
{//升序建大堆,降序建小堆,取决于AdjustDown函数中的符号for (int i = (n-1-1)/2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;//最后一个元素的下标while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}
七、归并排序(Merge Sort)
将数组分成两个子数组,递归地排序每个子数组,然后将每个子数组合并成一个新数组,直到整个原数组排序完成。
C语言实现
#include <stdio.h>int main()
{int n,m;scanf("%d%d",&n,&m);int a[n],b[m];//可用变长数组for(int i = 0; i < n; i++)scanf("%d",&a[i]);for(int i = 0; i < m; i++)scanf("%d",&b[i]);int add[n+m];int i = 0,j = 0;//分别指向两个数组的第一个元素int l = 0;while(i < n && j < m)//结束条件,防止越界{if(a[i] <= b[j])add[l++] = a[i++];else add[l++] = b[j++];}//还要考虑数组a或数组b中剩下的元素while(i < n){add[l++] = a[i++];}while(j < m){add[l++] = b[j++];}for(int e = 0; e < n+m; e++)printf("%d ",add[e]);return 0;
}
八、计数排序(Count Sort()
计数排序的基本思想是:通过统计每个元素出现的次数,然后根据这些统计信息构建有序的结果数组。
比如{1,5,2,1,7,5,5}这个数组中,1出现了2次,2出现了1次,5出现了3次,7出现了1次。
那么就排序为2个1,1个2,3个5,1个7。
C语言实现
#include <stdlib.h>
#include <string.h>
void CountSort(int* a, int n)
{int max = a[0], min = a[0];for (int i = 0; i < n; i++){if (a[i] > max)max = a[i];if (a[i] < min)min = a[i];}int range = max - min + 1;//范围int* countA = (int*)malloc(sizeof(int) * range);memset(countA, 0, range * sizeof(int));//初始化为0//统计每个元素出现的次数for (int i = 0; i < n; i++){countA[a[i] - min]++;}//排序int k = 0;for (int i = 0; i < range; i++){while (countA[i]--){a[k++] = i + min;}}
}
九、桶排序 (Bucket Sort)
C语言实现
十、基数排序 (Radix Sort)
C语言实现
总结
排序算法 | 优点 | 缺点 |
---|---|---|
冒泡排序 | 简单易实现 | 时间复杂度高,不适合 大规模数据 |
选择排序 | 简单易实现 | 时间复杂度高,不适合 大规模数据 |
插入排序 | 时间复杂度低,适合小规模数据 | 不适合大规模数据 |
希尔排序 | 时间复杂度低,适合大规模数据 | 不稳定 |
快速排序 | 时间复杂度低,不需要额外空间 | 不稳定 |
堆排序 | 时间复杂度低,不需要额外空间 | 不稳定 |
归井排序 | 时间复杂度低,稳定 | 需要额外空间 |
计数排序 | 时间复杂度低,适合数据范围较小的情况 | 需要额外空间 |
桶排序 | 时间复杂度低,适合数据范围较小的情况 | 需要额外空间 |
基数排序 | 时间复杂度低,适合数据范围较大, 但数据分布在较小范围内的情况 |
需要额外空间,时间复杂度 随着数据位数的增加而增 |
————————————————
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
原文链接:https://blog.csdn.net/m0_73900674/article/details/132418128