1插入类排序

（1）直接插入排序

　　算法大致流程：给定初始序列L，L从前往后依次取出一个数据，将其直接插入到有序序列中。

　　算法的复杂度分析：时间复杂度：最坏的情况下，每从无序序列中取一个元素，就要遍历一遍有序序列，复杂度为O（n²）；最好的情况下，每从无序序列中取出一个元素，直接放在了有序序列的后面，也就是不用遍历有序序列，此时，复杂度为O（n）。所以，平均复杂度为O（n²）。

　　　　　　　　　　　空间复杂度：O（1）

1 #include
     
       2 #define MAXSIZE 100 3 void out(int number[],int n) 4 { 5     for(int i=0; i
      
       j; --k)21                     number[k]=number[k-1];22                 number[j]=temp;23                 flag=1;24             }25             if(flag==1)26                 break;27         }28     }29     out(number,n);30 }31 32 int main()33 {34     int number[MAXSIZE];35     int n;36     scanf("%d",&n);37     for(int i=0; i

（2）折半插入排序

　　算法大致流程：给定初始序列L，L从前往后依次取出一个数据，将其插入到有序序列中，到这里和直接插入排序相同。不同之处就在于，插入到有序序列中时，由于其是有序的，我们就可以采用二分的方式快速找到该元素在有序序列中的位置。

　　算法的复杂度分析：时间复杂度：最坏的情况下，每从无序序列中取一个元素，就要遍历n/2个有序序列元素，复杂度为O（n²），最好的情况和直接插入排序一样，也是O（n）。平均复杂度为：O（n²）。

　　　　　　　　　　　空间复杂度：O（1）

（3）希尔排序（缩小增量排序）

　　算法大致流程：给定初始序列L，假设下标为0、1、2、3……n，例如，首先以5为增量分割序列，所以，0、5、10、15……为一组；1、6、11、16……为一组；2、7、12、17……为一组，将数列分为5组，这五组序列分别进行排序，构成一趟希尔排序。然后对排序后的整个数列，以3为增量分割序列，所以，0、3、6、9……一组；1、4、7、……一组，2、5、8、……一组，分为3组，对这三组数据分别进行排序，又做了一趟希尔排序。最后直到增量为1，就相当于整个序列作为一组进行一趟排序，从而使最终序列有序。

　　注：对于增量的选择，增量序列中没有除1以外的公因子，例如5、3、1就符合，8、4、2、1有公因子2，不符合。

　　算法的复杂度分析：时间复杂度：O（nlog₂n）

　　　　　　　　　　　空间复杂度：O（1）

2交换类排序

（1）冒泡排序

　　算法大致流程：给定初始序列L（含有n个元素），先用第0个元素和第1个元素比较，如果第0个元素比第1个元素大，则两个元素交换，否则什么都不做，然后第1个元素和2个元素比较，如果第1个元素大，则交换，一直进行下去，直到比较到n-2和n-1，完成一趟冒泡，最大的元素a被就冒上来，放在了正确的位置上（即最大的放在了最后）。然后采用相同的方法完成第二次冒泡，直到比较到n-3和n-2，那么除了a意外的其他所有元素的最大值最终放在了n-2的位置上……最后，只剩2个元素时，比较，交换，算法完成。在一趟冒泡过程中，没有元素交换，也结束算法。

　　算法的复杂度分析：时间复杂度：最坏情况下，每次都要交换，复杂度为O（n²），最好的情况是已经有序，复杂度为O（n）。平均复杂度为：O（n²）。

　　　　　　　　　　　空间复杂度：O（1）

1 #include 
     
       2  3 void swap(int *a,int *b) 4 { 5     int temp; 6     temp=*a; 7     *a=*b; 8     *b=temp; 9 }10 11 int main()12 {13     int i,j,n;14     int number[100000];15     scanf("%d",&n);16     for(int i=0;i
      
       0;--i)19     {20         for(j=0;j
       
        number[j+1])23             {24                 swap(&number[j],&number[j+1]);25             }26         }27     }28     for(i=0;i

（2）快排

　　算法的大致流程：给定初始序列L，任意选定某个数作为基准（一般选择序列的第一个数L[0]），从L[1]开始向右依次比较，第一次发现某个数L[k]比基准大的时候，交换L[0]和L[left]，此时的位置记为“left=left+1”，然后再开始从右往左查看，L[n-1]、L[n-2]……，当发现第一个比L[0]小的L[right]时候，交换L[0]和L[right]，此时记录位置为“right=right+1”，然后从L[left]开始向右看，重复上述过程，直到遇到比L[0]大的元素，记录位置，从L[right]开始向左看……直到left和right相遇，一趟快排完成，此时L[0]左边的元素均比L[0]小，L[0]右边的元素均比L[0]大。L[0]将L分成左右两部分，L和R。

　　对L和R分别执行和L一样的操作，直到最后分得的L和R中只有两个元素。

　　算法的复杂度分析：时间复杂度：最好的情况下是：O（nlog₂n），最坏的情况下是O（n²），待排序列越接近无序，效率越高，越有序，效率越低，排序的趟数和初始序列有关。平均复杂度为O（nlog₂n）。

　　　　　　　　　　　空间复杂度：需要借助栈，O（log₂n）

1 #include
     
       2 int n; 3 void quick_sort(int number[],int left,int right) 4 { 5     int a,b; 6     int start; 7     int temp; 8     if(left>=right) 9     {10         return;11     }12     temp=left;13     a=left;14     b=right;15     start=number[left];16     while(left
      
       =start&&right>left)20         {21             right--;22         }23         number[temp]=number[right];24         temp=right;25         while(number[left]<=start&&left

3选择类排序

（1）直接选择

　　算法大致流程：给定初始序列L（n个元素），从L中选择最小的值，和第一个元素交换，完成一次选择，此时有序序列的元素个数为1，无序序列的元素个数为n-1。接着对无序序列做相同的操作……直到无序序列个数为0，算法结束。

　　算法的复杂度分析：时间复杂度：平均复杂度为O（n²）。

　　　　　　　　　　　空间复杂度：O（1）

1 #include
     
       2 void swap(int *a,int *b) 3 { 4     int temp; 5     temp=*a; 6     *a=*b; 7     *b=temp; 8 } 9 10 int main()11 {12     int i,j,n;13     int number[1000];14     int point;15     scanf("%d",&n);16     for(i=0;i

（2）堆排序

　　堆：可看做一棵完全二叉树，对于每个非叶节点，满足父亲比孩子小（最小堆）或者父亲比孩子大（最大堆）。

　　算法大致流程：首先，用初始序列构建一棵完全二叉树，从最后一个非叶节点往前依次调整——比较他和它两个孩子的大小关系，若比两个孩子小，则将该父节点和两个孩子中较大的交换，即构建最大堆。

　　建立好最大堆时，第一趟排序完成，此时堆顶元素为最大元素，将他和最后一个元素交换，剩下的元素还是一棵完全二叉树，但是可能不满足堆的定义，将其重新构建为最大堆，（此时不满足最大堆的元素只有交换的那个值，所以，只需要调整那个值就可以了），将堆顶元素和最后一个元素交换，将剩下的元素构建最大堆，直到剩余元素只有1个，算法结束。

　　算法的复杂度分析：时间复杂度：最好和最坏的情况下复杂度均为O（nlog₂n）。

　　　　　　　　　　　空间复杂度：O（1）

4归并排序

二路归并排序

　　算法的大致流程：首先将初始序列L中每个元素作为一组，共分为n组。n组中相邻的两两归并，形成n/2（向上取整）组，将这些组内的元素进行排序，然后将这n/2（向上取整）组元素再两两归并，形成n/4（向上取整）组，将组内元素排序……重复这个操作，直到n/2^k=1，即最后归并为整个序列L，使之有序，算法结束。

　　算法的复杂度分析：时间复杂度：和初始序列无关，最好和最坏的情况下复杂度均为O（nlog₂n）。

　　　　　　　　　　　空间复杂度：需要转存序列，空间复杂度为O（n）