1、冒泡排序
冒泡排序算法的运作如下:
(1)临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,
(2)这样一趟过去后,最大或最小的数字被交换到了最后一位,
(3)然后再从头开始进行两两比较交换,直到倒数第二位时结束。
冒泡排序总的平均时间复杂度为
1 void bubble_sort(int a[], int n) 2 { 3 int i, j, temp; 4 for (j = 0; j < n - 1; j++) 5 { 6 for (i = 0; i < n - 1 - j; i++) 7 { 8 if(a[i] > a[i + 1]) 9 {10 temp = a[i];11 a[i] = a[i + 1];12 a[i + 1] = temp;13 }14 }15 }16 }
View Code
2、快速排序
快速排序是对冒泡排序的一种改进,它的基本思想是: 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。 设要排序的数组是A[0]… … A[N-1],首先任意选取一个数据作为关键数据,然后将所有比它小的数据都放到它前面,所有比它大的数据都放到它后面,这个过程称为一趟快速排序。 值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。
1 int FindPos(int *a, int low, int high) 2 { 3 int val = a[low]; 4 5 while (low < high) 6 { 7 while ((low < high) && (a[high] >= val)) 8 { 9 --high;10 }11 a[low] = a[high];12 13 while ((low < high) && (a[low] <= val))14 {15 ++low;16 }17 a[high] = a[low];18 } 19 a[low] = val;20 21 return high;22 }23 24 void QuickSort(int *a, int low, int high)25 {26 int pos;27 28 if (low < high)29 {30 pos = FindPos(a, low, high);31 QuickSort(a, low, pos-1);32 QuickSort(a, pos+1, high);33 }34 }
View Code
3、插入排序
插入排序算法的运作如下:
(1)
4、希尔排序
希尔排序算法的运作如下:
(1)
5、选择排序
选择排序算法的运作如下:
设有10个元素a[1]~a[10],将a[1]与a[2]~a[10]比较,若a[1]比a[2]~a[10]都小,则不进行交换。若a[2]~a[10]中有一个以上比a[1]小,则将其中最小的一个与a[1]交换,此时a[1]中存放了10个中最小的数。第二轮将a[2]与a[3]~a[10]比较,将剩下的最小者与a[2]对换,此时a[2]中存放的是10个中第二小的数,依此类推。
1 for (i = 0; i < 9; i++) 2 { 3 min = i; 4 for (j = i+1; j < 10; j++) 5 { 6 if (a[min] > a[j]) 7 { 8 min = j; 9 }10 }11 temp = a[i];12 a[i] = a[min];13 a[min] = temp;14 }
View Code
6、归并排序
归并排序算法的运作如下:
(1)
只剩下一条路,那就是成功的路。