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 }
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 }
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 }
6、归并排序
归并排序算法的运作如下:
(1)
- 还没有人评论,欢迎说说您的想法!