排序算法，排序

排序算法，排序

排序

1. 直接插入排序

原理：將當前無序區a[i...n-1]的記錄一個一個插入到有序區a[0....i-1]合適位置；

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

2. shell 排序

原理:實質為分組插入排序，首先按增量為d分成若干組，下標相差d的元素放在一組使用直接插入排序；然後用一個較小的增量繼續分組和排序，直至增量減到1，整個分組即為一組，排序完成。

 1 void shell_sort(int *a, int n)
 2 {
 3     for(int h=n/2;h>0;h=h/2)
 4     {
 5          for(int i=h;i<n;i++)                     //for 循環就是增量為h的直接插入排序
 6          {
 7              int temp=a[i];
 8              int j;
 9              for(j=i-h;j>=0&&temp<a[j];j=j-h)
10              {
11                  a[j+h]=a[j];
12              }
13              a[j+h]=temp;
14          }
15     }
16 }

3. 冒泡排序

原理:首先將a[0...n-1] 垂直排列，根據氣泡原理，較輕的會浮在較重的上面。 自底向上掃描：凡掃描到違反此原則的輕氣泡，就使其上浮。

每遍掃描都會是最輕的一個元素上浮。掃描n-1 趟

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