本文共 2760 字，大约阅读时间需要 9 分钟。

1.冒泡排序

基本思想：每次遍历数组，相邻的两个元素比较，（升序时）如果后面小于前面那么就交换这两个数，每次循环结束时使得一个最大数冒泡至数组尾部。最终实现全部排序。

时间复杂度：o(n^2) 空间复杂度：o(1)

优化：由于冒泡排序在进行排序时，遍历一次的同时可以判断该数组是否有序，因而在排序时可以判断如果当前数组有序，即可以退出排序。

void bubble_sort(int a[],int n){    int i,j,t,f;    for(i=0;i

2.选择排序

基本思想：选择首个元素和后面的元素依次比较，若符合条件则交换，一次循环可使得首个位置的数字确定，依次向后进行，可使整个数组有序。

时间复杂度：o(n^2) 空间复杂度：o(1)

优化：不好优化。

void selection_sort(int a[],int n){    int i,j,t;    for(i=0;i
   
    a[j])                t=a[j],a[j]=a[i],a[i]=t;}
   

3.插入排序

基本思想：前提为当前部分数组已经有序，若要将一个数插入到该数组中使其依然有序，则只需找到该数字因插入的位置并将其他元素依次平移，使该元素插入。在一个无序的数组中进行插入排序，只需将其中某单个元素确定为有序，其他元素依次插入。

时间复杂度：o(n^2) 空间复杂度：o(1)

优化：可在查找位置时利用二分查找进行优化，可以减少比较次数，但是并不能减少移动次数。故时间复杂度依旧是o(n^2) 

void insertion_sort(int a[],int n) //直接插入版{    int i,j,k;    for(i=1;i
   
    0&&k
   

int search(int a[],int n,int x,int y) //二分插入版{    int mid=x+(y-x)/2;    if(n>a[y]) return y+1;    if(n
   
    =n) return mid+1;        else if(n
    
     a[mid]) return search(a,n,mid+1,y);}void insertion_sort(int a[],int n){    int i,j,k,x;    for(i=1;i
     
      x;j--)            a[j]=a[j-1];        a[j]=k;    }}
     
    
   

4.快速排序

基本思想：选出一个数M使其左边的数小于M右边的数大于M，然后最左右两边递归，利用相同的方式划分，最终实现全部有序。

时间复杂度：o(nlogn) 空间复杂度：o(1)

优化：由于快速排序最坏情况是数组已经有序此时时间复杂度o(n^2)，所以可以在选择M时使用随机选择，以使得其划分更加有效。

void quick(int low,int high){    int i=low,j=high,x=a[high];    if(low>=high) return;    while(j>i)    {        while(j>i&&a[i]<=x) i++;        a[j]=a[i];        while(j>i&&a[j]>=x) j--;        a[i]=a[j];    }    a[i]=x;    quick(low,i-1);    quick(i+1,high);}

5.堆排序

基本思想：在完全二叉树下构建一棵大根树，使得根最大，然后把根与末尾子叶交换，并且将末尾一个节点剪掉，剩下的继续构建为大根树，如此循环，直到剩下一个节点为止。即数组已经完成排序。

时间复杂度：o(nlogn)  空间复杂度：o(1)

优化：暂时没有了解。

我的理解：

前几种排序之前都有过接触，而且代码也都写过，所以比较顺手，但是这个堆却是第一次接触，包括树这种数据结构以及二叉树的一些定义都是今天才真正了解，今天听学长讲完之后，也是似懂非懂，所以就试着写了一下堆排序的代码。

其实刚开始时感觉挺难操作，于是并没有急于写代码，而是先分析理解了二叉树的特点，以及大根树的定义，以及排序的原理。考虑递归应该把握的原则，以及情况分类，然后试着在纸上写出伪代码。这也是我第一次用伪代码去描述算法，感觉非常好用。实现的过程还是比较顺利的，唯一一点疏忽的就是在输出时顺手写成了for（i=0;i<n;i++），——！找了半天才找到。

第一部分是构建大根树，要用到递归。用递归就要思考递归出口，和递归原则。原则很简单就是“爹比儿子大”，出口就是“他没有儿子”。

第二部分是交换位置。大根和末尾的儿子交换、重新构建大根树。实现并不困难，只是注意每次都要将末尾节点去除。

#include
   
    int a[1001]={0,21,12,53,24,59,234,43,22,13,15}; ///a[0]不存放数据。build_tree(int a[],int dad,int n) ///n:整个树的节点数。a[n]存在。{    int s1=2*dad,s2=2*dad+1;    if(dad*2>n) return; ///递归出口    build_tree(a,s1,n);    build_tree(a,s2,n);    if(s2<=n) ///双叉情况    {        if(a[dad]>=a[s1]&&a[dad]>=a[s2]) return;        else if(a[s1]>a[dad]&&a[s1]>a[s2])                    a[0]=a[s1],a[s1]=a[dad],a[dad]=a[0];            else a[0]=a[s2],a[s2]=a[dad],a[dad]=a[0];    }    else if(a[s1]>a[dad]) ///单叉情况        a[0]=a[s1],a[s1]=a[dad],a[dad]=a[0];}tree_sort(int a[],int n){    while(n>1)    {        build_tree(a,1,n);        a[0]=a[1],a[1]=a[n],a[n]=a[0];        n--;    }}
   

转载地址：http://ttrhi.baihongyu.com/