以下三种排序算法的时间复杂度是O(n2)。在这三种排序算法中,比较好的是插入排序。 (1) 插入排序! 基本思想:假设前 i 个元素已经排好序,然后把第 i+1个元素插入到合适的位置上。 void ins_sort(int *a, int start, int end) { int j,k; for (int i=start+1; i<end; i++) { for (k=a,j=i-1; k<a[j] && j>=start; j--) a[j+1]=a[j]; a[j+1]=k; } } |
(2) 选择排序! 基本思想:处理第 i 个元素时,找到它后面所有数的最小值。如果这个最小值比它小,就互相交换。 void swap_sort(int *a, int start, int end) { int temp; for (int i=start; i<end; i++) for (int j=i+1; j<end; j++) if (a>a[j]) temp=a,a=a[j],a[j]=temp; } |
(3) 冒泡排序! 基本思想:对相邻两个元素进行比较,并将较小的数放到前面。重复 n 组即可完成排序。 void bubble_sort(int *a, int start, int end) { int temp; for (int i=start; i<end; i++) | | for (int j=end; j>i; j--) // 从start到i,在“冒泡”过程中,元素已经排好序。 if (a[j-1]>a[j]) temp=a[j-1], a[j-1]=a[j], a[j]=temp; |
|