几种内排序算法

排序算法可以说是最基本的算法，再熟悉不过了。习惯了使用STL的sort函数，若要自己来实现几种排序方法，真的能够准确无误的写出来吗？（以下排序算法均默认从小到大排序）。

1.简单选择排序

算法思想：每次从未排序数组中选择最小数，跟排序后它对应位置元素交换。

时间复杂度：最好，平均，最坏都为O(n²)。

适用：元素较少的数组。

 1 void SelectSort(int a[],int length)
 2 {
 3     int i,j;
 4     for(i=0;i<length;i++)
 5     {
 6         int small=i;
 7         for(j=i+1;j<length;j++)
 8         {
 9             if(a[j]<a[small])
10             {
11                 small=j;
12             }
13         }
14         swap(a[i],a[small]);
15     }
16 }

2.直接插入排序

算法思想：依次遍历数组，将当前元素插入到已排序好数组中。

时间复杂度：最好O(n)，最坏O(n²)

适用：基本有序数组。因为算法必须进行n-1次排序，若数组基本有序，每次之比较一次，移动元素两次。

 1 void InsertSort(int a[],int length)
 2 {
 3     int i,j;
 4     for(i=0;i<length;i++)
 5     {
 6         int temp=a[i];
 7         j=i;
 8         while(j>0&&temp<a[j-1])
 9         {
10                 a[j]=a[j-1];
11                 j--;
12         }    
13         a[j]=temp;
14     }
15 }

3.冒泡排序

算法思想：依次比较相邻两个元素，最大数沉底。

时间复杂度：最好O(n)，最坏O(n²)。

适用：基本有序的数组。若已有序，只需排序一次，比较n-1次。

 1 void BubbleSort(int a[],int length)
 2 {
 3     int i,j,last;
 4     i=length-1;
 5     while(i>0)
 6     {
 7         last=0;
 8         for(j=0;j<i;j++)
 9         {
10             if(a[j]>a[j+1]) 
11                 swap(a[j],a[j+1]);
12             last=j;
13         }
14         i=last;
15     }
16 }

4.*快速排序

算法思想：每次将待排数组分为两部分，一部分小于分割元素，一部分大于分割元素。

时间复杂度：平均O(nlog₂n），空间复杂度O(n)。

适用：偏爱基本无序数组，适合数组元素多。快速排序时目前最快的排序算法。

改进：1.递归算法效率不如非递归算法，可以用栈保存子序列上下界来消除递归。也可以用队列消除递归。

2.先对短的序列排序，长的子序列后排序。

 1 void QuickSort(int a[],int left,int right)
 2 {
 3     if(left<right)
 4     {
 5         int i=left;
 6         int j=right;
 7         do
 8         {
 9             do i++;while(a[i]<a[left]);
10             do j--;while(a[j]>a[left]);
11             if(i<j) swap(a[i],a[j]);
12         }while(i<j);
13         swap(a[left],a[j]);
14         QuickSort(a,left,j);
15         QuickSort(a,j+1,right);
16     }
17 }

5.合并排序

算法思想：数组元素两两合并成一个子序列，子序列继续两两合并。

时间复杂度：O(nlog₂n),空间复杂度O(n)。

 1 void Merge(int a[],int i1,int j1,int i2,int j2)
 2 {
 3     int *Temp=new int[j2-i1+1];
 4     int i=i1,j=i2,k=0;
 5     while(i<=j1&&j<=j2)
 6     {
 7         if(a[i]<=a[j])
 8             Temp[k++]=a[i++];
 9         else Temp[k++]=a[j++];
10     }
11     while(i<=j1) Temp[k++]=a[i++];
12     while(j<=j2) Temp[k++]=a[j++];
13     for(i=0;i<k;i++)
14         a[i1++]=Temp[i];
15     delete[] Temp;
16 }
17 void MergeSort(int a[],int length)
18 {
19     int i1,i2,j1,j2;
20     int size=1;
21     while(size<length)
22     {
23         i1=0;
24         while(i1+size<length)
25         {
26             i2=i1+size;
27             j1=i2-1;
28             if(i2+size-1>length-1)
29                 j2=length-1;
30             else
31                 j2=i2+size-1;
32             Merge(a,i1,j1,i2,j2);
33             i1=j2+1;
34         }
35         size*=2;
36     }
37 }

6.堆排序

算法思想：利用最大堆原理，将堆顶元素跟排序后它对应的位置元素交换。

时间复杂度：O(nlog₂n)

 1 void AdjustDown(int a[],int r,int j)
 2 {
 3     int child=2*r+1;
 4     int temp=a[r];
 5     while(child<=j)
 6     {
 7         if((child<j)&&(a[child]<a[child+1]))
 8             child++;
 9         if(temp>=a[child])
10             break;
11         a[(child-1)/2]=a[child];
12         child=2*child+1;
13     }
14     a[(child-1)/2]=temp;
15 }
16 
17 void HeapSort(int a[],int length)
18 {
19     int i;
20     for(i=(length-2)/2;i>=0;i--)
21         AdjustDown(a,i,length-1);
22     for(i=length-1;i>0;i--)
23     {
24         swap(a[0],a[i]);
25         AdjustDown(a,0,i-1);
26 
27     }
28 }

几种内排序算法

推荐阅读