【排序算法】各种排序算法的主要方式和复杂度分析

概念

1，排序：按关键字有序的序列
2，稳定性：假设ki=kj(1<=i,j<=n,i≠j)，且在排序前ri领先于rj（即i 3，内排序：排序过程中，将待排的所有记录全部放在内存中。
性能指标：
①时间性能：关键字比较次数和记录移动次数（都尽可能少）
②辅助空间
③算法的复杂度：算法本身的复杂度（？）
4，外排序：由于记录的个数太多，不能同时放置在内存中，整个排序需要在内外存之间多次进行数据交换才能实现。
5，分类
从难易程度：冒泡排序，简单选择排序，直接插入排序比较简单，希尔排序，堆排序，归并排序，快速排序属于改进算法。
6，排序中常用到交换的操作，写代码时拎出来写。以下都是按照升序排列。

冒泡排序

基本思想：
比较两两相邻的关键字，如果反序则交换，直到没有反序的记录为止。
代码示例：

void BubbleSort0(SqList *L) {int i,j;for(i=1;ilength;i++){for(j=i+1;jlength;j++){if(L->[i]>L->[j]){//交换值swap(L,i,j);}}}}

正宗冒泡排序：

void BubbleSort(SqList *L) {int i,j;for(i=1;ilength;i++){for(j=L->length-1;j>i;j--){if(L->[j] > L->[j+1]){swap(L,j,j+1);}}}}

复杂度：O(n^2)

简单选择排序

通过n-i次比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录交换之。(通过记录下标避免了多次交换)
代码示例：

void SelectSort(){int i,j,min;for(i=0;ilength;i++){int min = i;for(j=i+1;jlength;j++){if(L->[min] > L->[j]){min = j;}}if(i != min){swap(L,i,min);}}}

复杂度：O(n^2)

直接插入排序

将一个记录插入到已经排好序的有序表中，从而得到一个有序的新增记录为1的有序表。
代码示例：

void InsertSort(SqList *L){int i,j;for(i=2;ilength;i++ ){if(L->[i][i-1]){L->[0] = L->[i];for(j=i-1;L->[j]>L->[0];j--){L->[j+1] = L->[j];}L->[j+1] = L->[0];}}}

复杂度：O(n^2)

总结

虽然复杂度一样，但是性能具体来说，直接插入>简单选择>冒泡