C语言实现各种排序算法实例代码(选择,冒泡,插入,归并,希尔,快排,堆排序,计数)
目录
- 前言
- 选择排序
- 冒泡排序
- 插入排序
- 归并排序
- 希尔排序
- 快速排序
- 堆排序
- 计数排序
- 总结
前言
平时用惯了高级语言高级工具高级算法，难免对一些基础算法感到生疏。但最基础的排序算法中实则蕴含着相当丰富的优化思维，熟练运用可起到举一反三之功效。
选择排序
选择排序几乎是最无脑的一种排序算法，通过遍历一次数组，选出其中最大（小）的值放在新数组的第一位；再从数组中剩下的数里选出最大（小）的，放到第二位，依次类推。
算法步骤
设数组有n个元素，{ a 0 , a 1 , … , a n }
由于每次遍历需要计算O ( n ) 次，且需要便利n 次，故时间复杂度为O ( n 2 ))；由于只在交换的过程中需要额外的数据，所以空间复杂度为O ( n ) 。
C语言实现
//sort.c
void SelectionSort(double *p, int n);
int main(){
double test[5] = {3,2,5,7,9};
SelectionSort(test,5);
for (int i = 0; i < 5; i++)
printf(\”%f\\n\”, test[i]);
return 0;
}
//交换数组中i,j处的值
void mySwap(double *arr, int i, int j){
double temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//选择排序
void SelectionSort(double *arr, int n){
int pMax;
double temp;
for (int i = 0; i < n-1; i++){
pMax = i;
for (int j = i+1; j < n; j++)
if (arr[j]>arr[pMax])
pMax = j;
mySwap(arr,pMax,i);
}
}
验证
>gcc sort.c
>a
9.000000
7.000000
5.000000
3.000000
2.000000
冒泡排序
冒泡排序也是一种无脑的排序方法，通过重复走访要排序的数组，比较相邻的两个元素，如果顺序不符合要求则交换两个数的位置，直到不需要交换为止。
算法步骤
设数组有n个元素，{ a 0 , a 1 , … , a n }
由于每次遍历需要计算O ( n ) 次，且需要遍历n次，故时间复杂度为O ( n 2 ) ，空间复杂度为O ( n ) 。
C语言实现
//冒泡排序
void BubbleSort(double *arr, int n)
{
n = n-1;
double temp;
for (int i = 0; i < n; i++)
for (int j = 0; j < n-i; j++)
if (arr[j]>arr[j+1])
mySwap(arr,i,j); /*前文定义的函数*/
}
插入排序
插入排序是算法导论中的第一个算法，说明已经不那么无脑了。其基本思路是将数组划分位前后两个部分，前面是有序数组，后面是无序数组。逐个扫描无序数组，将每次扫描的数插入到有序数组中。这样有序数组会越来越长，无序数组越来越短，直到整个数组都是有序的。
算法步骤
设数组有n个元素，{ a 0 , a 1 , … , a n }
可见，插入排序的每次插入都有O ( n )的复杂度，而需要遍历n nn次，所以时间复杂度仍为O ( n 2 ) 。
C语言实现
//插入排序
void InsertionSort(double *arr, int n){
double temp;
int j;
for (int i = 1; i < n; i++){
j = i-1;
temp = arr[i];
while (temp<arr[j] && j>=0){
arr[j+1] = arr[j]; //第j个元素后移
j–;
}
arr[j+1] = temp;
}
}
归并排序
归并排序是算法导论中介绍分治概念时提到的一种排序算法，其基本思路为将数组拆分成子数组，然后令子数组有序，再令数组之间有序，则可以使整个数组有序。
算法步骤
设数组有n个元素，{ a 0 , a 1 , … , a n }
