常见排序算法总结.docVIP

常见排序算法总结 虽然现有的开发组件中对排序算法已经有很好的实现，但是通过研究这些算法的思路，对我们思维能力的提高还是很有帮助的，以下都以升序为例，总结如下。 1.冒泡排序，最简单也最常用的一种(^_^不复习的情况下，笔试遇到排序问题，我只能记住它)，思想是：每次将数组前N个中最大（升序）或最小（降序）的数交换到数组底部，每次数组大小N--，再进行如此操作，直到所有的数都已排序即N=1。这样循环比较的次数是（n-1）+(n-2)+(n-3)....... 约等于(n)(n+1)/2, 时间复杂度为O(n2),N的平方。C语言实现如下： void bubble_sort(int *array, int size){ int i, j, temp; for (i=size-1; i1; i--) for (j=0; ji; j++) if (array[j] array[j+1]) { temp = array[j+1]; array[j+1] = array[j]; array[j] = temp; }} 2.交换排序，原理是用第一个元素和第二个元素比较，若第一个元素大于第二个，则交换，交换后第一个元素在与第三个元素比较.....直到N个元素，然后再选择第二个元素和第三个元素比较，进行同样操作.....直到选择到N个元素。这样操作完成后数组就变为升序了。其实说白了，原理就是第一次交换，确保第一个元素是最小的，第二次交换确保第二个元素是第二小的.... 以此类推。效率也很低，循环次数(n-1)(n-2)..即O(n2), n的平方，C语言实现如下： void change_sort(int *array, int size){ int i, j, temp; for (i=0; isize; i++) for (j=i+1; jsize; j++) if (array[i]array[j]){ temp = array[j]; array[j] = array[i]; array[i] = temp; }} 3.选择排序，仔细看交换排序，发现其实没必要每次发现比自己小的元素就发生交换，只要和剩下的元素中最小的那个元素交换就可以了，即选择最小的元素进行交换，那么交换排序的扩展算法，选择排序就很容易得出来了，效率略比交换排序高，整体平均效率还是N的平方，C语言实现如下： void select_sort(int *array, int size){ int i, j, temp, pos; for (i=0; isize; i++) { for (j=i+1, temp=array[i], pos=i; jsize; j++) if (temp array[j]) { temp = array[j]; pos = j; } array[pos] = array[i]; array[i] = temp; }} 4.插入排序,有点类似冒泡排序的逆操作，也是比较简单易懂的算法。原理是，现对数组第一个和第二个排序，这样前2个元素就是有序的了，再引入第三个元素，找到合适的位置插入。。。以此插入剩余元素。这种排序算法比起冒泡排序算法效率更高，有点类似冒泡排序的改进算法。虽然效率上比冒泡排序好，但是也是一种简单排序算法，循环次数为 1+2+3...+n-1,即n(n+1)/2, 平均情况