排序演算法: 氣泡排序, 快速排序,希爾排序,直接插入排序 ,直接選擇排序,歸併排序,堆排序

NO IMAGE

幾種排序演算法分析:

 

  氣泡排序

  氣泡排序的方法排序速度比較慢。

  思路:進行n-1排序,第一次排序先找出最小的數字,放在第一個位置,然後在剩餘的數字中再找出最小的數字,放在第二個位置上,依次類推,可以排出所有的數字。

  當然也可以從大到小的排序。

  例如 a[]={5 ,4 ,3, 2, 1};

    

   void maopao(int a[] ,int n)

{

           int i , j, tmp;

           for(i = 0 ;i <n-1 li )

         

        {

                  for(j = 0 ;j <n-1-i ; j )

                   {

                        if(a[j]>a[j=1])

                         {

                                 tmp = a[j];

                     a[j] = a[j 1];

a[j 1] = tmp;

                         }

                  }

        }

}

  氣泡排序的時間複雜度是,最好的情況下為 n-1  即O(n)    交換次數為 0

  最壞的情況下的時間複雜度為 進行n-1排序 第一次排序 需要進行n-1 次遍歷,第二次排序需要遍歷n-2次遍歷 ,依次類推 一直到 1次遍歷。

   (((n-1) 1)/2)*(n-1); 時間複雜度為 O(n^(2))  。交換次數為 (((n-1) 1)/2)*(n-1)*3 。

平均的時間複雜度為 O(n^(2)) 。

氣泡排序屬於穩定的排序演算法。

 

 快速排序:

  

 快速排序是對氣泡排序的一種改進。它的基本思想是:通過一躺排序將要排序的資料分割成獨立的兩部分,其中一部分的所有資料都比另外一不部分的所有資料都要小,然後再按次方法對這兩部分資料分別進行快速排序,整個排序過程可以遞迴進行,以此達到整個資料變成有序序列。

     a[N] ={ 3 , 2 , 4 , 5 , 1};

    i j,

   i=0;

  j = 4;

     首先要先確定第一次比較的基準值,一般是選擇第一個資料作為基準值,選擇  a[0] = 3 作為 temp = 3;

     從陣列後面開始比較

     a[4]< tmp  那麼把a[4]設定為 3  a[0]設為1

    此時變為 : { 1 , 2 ,4 ,5 ,3}

   這時從陣列前面開始比較

     a[0]< 3 ,a[1]<3 ,只有a[2]>3 .此時把 a[2 ]設為 3 ,a[4]設定為 4

  此時變為

     { 1 ,2 ,3, 5, 4}

   此時的     從後邊開始 a[3]= 5 >3 , j–

 此時 i = 2 ,j = 2 不符合  i<j條件,本次階數

最後結果為

   {1 ,2 , 3, 5,4}

 這樣就 把陣列分成了兩組 ,再用此類方法分別對這兩個組進行 這種排序,最後得到是;

 { 1,2,3,4,5}

     具體的程式碼如下:

   

void quicksort(int a[],int left ,int right)
{
 int i ,j ,tmp;
 i = left ;
 j = right;
 tmp = a[left];
 if(left > right)
 {
  return;
 }
 while(i != j)
 {
  while(a[j]>=tmp && j>i)
  {
   j–;
  }
  if(j>i)
  {
   a[i ] = a[j];
  }
  while(a[i]<=tmp && j>i)
  {
   i ;
  }
  if(j>i)
  {

   a[j–] = a[i];
  }
 }
 a[i] = tmp;
 quicksort(a,left ,i-1);
 quicksort(a,i 1 ,right);
}

void main()
{
 int a[]={3,2,4,5,1};
 int i;
 quicksort(a,0,4);
 for(i =0;i<5 ;i )
 {
  printf(“%4d”,a[i]);
 }
}

 

快速排序的方法速度比較快,但是排序不穩定

 

 希爾排序:

希爾排序的實質就是分組插入排序,該方法又稱縮小增量排序,因DL.Shell於1959年提出而得名。

 

該方法的基本思想是:先將整個待排元素序列分割成若干個子序列(由相隔某個“增量”的元素組成的)分別進行直接插入排序,然後依次縮減增量再進行排序,待整個序列中的元素基本有序(增量足夠小)時,再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本有序的情況下(接近最好情況),效率是很高的,因此希爾排序在時間效率上比前兩種方法有較大提高

 

 例如:

 49  38  65  97  76  13  27  49  55   4

這10個數

首先增量的步長為 10/2 = 5 就是分成5個組 每個組是2兩個資料

 小組     1    2    3    4    5         

           49   38  65  97  76

           13   27  49  55   4 

這樣在每個小組內進行的直接插入排序 後結果為

           13   27   49  55   4

           49   38     65  97  76

13  27   49   55   4  49  38  65   97  76

第一次拍完後,進行第二次排序,這是步長為 5/2 = 2 分成2個小組

 小組   1    2

           13   27

           49    55

           4      49

           38     65

            97   76

每個小組內進行直接插入排序  結果為:

          4     27

          13    49

          38     55

         49       65

        97       76

結果為

4  27  13  49   38  55  49  65  97  76 

第二次排序完成,第三次排序的補償為 2/2 = 1

對一個小組進行直接插入排序:

 

4  13  27  38  49   49  55  65  76  97  

 

 

這樣就已經排序完成

具體程式碼如下:

 //希爾排序的 從小到大的排序

 void shellsort(int a[] ,int len)

{

        int i ,j , k,gap ,temp;

       for( gap = len/2 ; gap >0 ; gap = gap/2)

       {

                   for(i = 0 ;i<gap ;i )

                   {

                              for( j = i gap ; j <len ; j =j gap )

                               {

                                     if( a[j]<a[j-gap] )

                                     {

                                            temp = a[j];

                                            k = j-gap;

                                           while( (k>=0) && (a[k] >temp))

                                           {

                                                 a[k gap] = a[k];

                                                  k = k-gap;

                                           }

                                          a[k gap] = temp;

                                      }

                               }

                   }

       }

       

}

 

#include <iostream>
using namespace std;
void shellsort(int a[] ,int len)
{
int i ,j , k, gap ,temp;
for( gap = len/2 ; gap >0 ; gap = gap/2)
{
for(i = 0 ;i<gap ;i  )
{
for( j = i gap ; j <len ; j =j gap )
{
if( a[j]<a[j-gap] )
{
temp = a[j];
k = j-gap;
while( (k>=0) && (a[k] > temp))
{
a[k gap] = a[k];
k = k-gap;
}
a[k gap] = temp;
}
}
}
}
}
void main()
{
int a[]={6,3,5,2,4,1};
shellsort(a, 6);
int i ;
for(i = 0 ;i<6 ;i  )
{
cout<<a[i];
}
}

 

 

 //希爾排序的 從大到小的排序

 void shellsort(int a[] ,int len)

{

        int i ,j , k,gap ,temp;

       for( gap = len/2 ; gap >0 ; gap = gap/2)

       {

                   for(i = 0 ;i<gap ;i )

                   {

                              for( j = i gap ; j <len ; j =j gap )

                               {

                                     if( a[j] > a[j-gap] )

                                     {

                                            temp = a[j];

                                            k = j-gap;

                                           while( (k >= 0) && (a[k]  < temp))

                                           {

                                                 a[k gap] = a[k];

                                                  k = k-gap;

                                           }

                                          a[k gap] = temp;

                                      }

                               }

                   }

       }

       

}

 

 直接插入排序:

 

 

例如 a[]={3 ,4,2,1,5};

len = 5;

首先先進行的是 a[1] 進行排序 與a[0]進行比較一下。但是a[1] 是大於 a[0]的。所以a[0] = 3 ,a[1] = 4

然後再比較a[2] = 2 ,與a[1]= 4 .a[0] = 3 進行比較

與a[1] 比較後 小於 4 則把 a[2] 設為 4  a[1] 設為 3 ,此時把a[0] 設定為 2

此時a[0] = 2   a[1] = 3   a[2] = 4

然後在比較a[3] = 1 同樣,a[3] 小於 a[2] a[1] a[0]

 a[3] = 4;

a[2] = 3;

a[1] = 2;

a[0] = 1;

然後再比較 a[4 ] =5 大於之前所有的數,所以呢,最後的排序為;

 

a[]={1,2,3,4,5};

 

 直接插入排序 從小到大排序

void insersort(int a[] ,int len)

{

         int i ,j ,tmp;

         for(i = 1 ;i <len ;i )

         {

                 tmp = a[i];

                 j = i-1;

                 while(j>=0 &&(tmp<a[j]))

                 {

                        a[j 1] = a[j]

                        j–;

                 }

                 a[j 1] = tmp;

         }

}

 

// 直接插入排序 從大到小
void instersort(int a[] , int len)
{
 int i ,j,tmp;
 for(i = 1;i<len ;i )
 {
  tmp = a[i];
  j = i-1;
  while((j>=0)&&(a[j] < tmp))
  {
   a[j 1] = a[j];
   j–;

  }
  a[j 1] = tmp;
 }
}

 

(1)時間複雜度
            從時間分析,首先外層迴圈要進行n-1次插入,每次插入最少比較一次(正序),移動兩次;最多比較i次,移動i+2次(逆序)(i=1,2,…,n-1)。若分別用Cmin
            ,Cmax 和Cave表示元素的總比較次數的最小值、最大值和平均值,用Mmin ,Mmax
            和Mave表示元素的總移動次數的最小值、最大值和平均值,則上述直接插入演算法對應的這些量為:
            Cmin=n-1 Mmin=2(n-1)
            Cmax=1 2 … n-1=(n2-n)/2 Mmax=3 4 … n 1=(n2 3n-4)/2
            Cave=(n2 n-2)/4 Mmax=(n2 7n-8)/4
            因此,直接插入排序的時間複雜度為O(n2)。

            由上面對時間複雜度的分析可知,當待排序元素已從小到大排好序(正序)或接近排好序時,所用的比較次數和移動次數較少;當待排序元素已從大到小排好序(逆序)或接近排好序時,所用的比較次數和移動次數較多,所以插入排序更適合於原始資料基本有序(正序)的情況.

            插入法雖然在最壞情況下複雜性為O(n2),但是對於小規模輸入來說,插入排序法是一個快速的排序法。許多複雜的排序法,在規模較小的情況下,都使用插入排序法來進行排序,比如快速排序。

            (2)空間複雜度
            首先從空間來看,它只需要一個元素的輔助空間,用於元素的位置交換O(1)
            (3)穩定性:
            插入排序是穩定的,因為具有同一值的元素必然插在具有同一值得前一個元素的後面,即相對次序不變.
            (4)結構的複雜性及適用情況
            插入排序是一種簡單的排序方法,他不僅適用於順序儲存結構(陣列),而且適用於連結儲存結構,不過在連結儲存結構上進行直接插入排序時,不用移動元素的位置,而是修改相應的指標。

 

 

直接選擇排序:

 

 void selectsort(int a[] ,int len)

{

      int i ,j ,k ,tmp ,t;

      for(int i = 0 ;i<len ;i )

      {

            k = i;

            for(j = i 1 ; j<len ;j )

            {

                   if(a[j] < a[k])

                   {

                           t = 1;

                   }

                   if(t == 1)

                  {

                       tmp = a[i];

                         a[i] = a[j];

                        a[j] = tmp;

                    }

                   t =0;

            }

      }

}

 

歸併排序 :

歸併排序是前提是紀錄已經排好的陣列,把他們合併到一起而已。

例如

a1[]={ 2 , 4 , 7 , 8};

a1[]={1 ,  3 ,  5  ,  9};

 

先自己開闢一個空間

int *a=(int*)malloc(len*sizeof(int));

 

 

void merge(int a[] , int low ,int m ,int high)
{
 int i = low;
 int j = m 1;
 int p = 0;
 int *a1=(int*)malloc((high-low 1)*sizeof(int));
 if(a1 == NULL)
 {
  printf(“error”);
 }
 while((i<= m) && (j<=high))
 {
  if(a[i]>=a[j])
  {
   a1[p] = a[j];
   p ;
   j ;
   //i ;
  }
  if(a[i]<=a[j])
  {
   a1[p] = a[i];
   p ;
   i ;
   //j ;
  }
 
 }
 while(i<=m)
 {
  a1[p] = a[i];
  p ;
  i ;
 }
 while(j<= high)
 {
  a1[p] = a[j];
  p ;
  j ;
 }
 for(p = 0 ,i = low ;i<=high ;p ,i )
 {
  a[i] = a1[p];
 }
}

 

堆排序:

時間複雜度為O(nlogn),空間複雜度為1

#include <iostream>
using namespace std;
void sift(int a[] ,int k ,int n)
{
int i ,j ,tmp,x;
i = k;
x = a[i];
bool finished  = false;
j = 2*i;
while(j<=n&&(!finished))
{
if(j<n&&(a[j]>a[j 1]))
{
j = j 1;
}
if(x<=a[j])
{
finished = true;
}
else
{
a[i] = a[j];
i = j;
j = 2*i;
}
}
a[i] = x;
}
void heapsort(int a[] ,int n)
{
int m ,tmp,i,j;
m = n/2;
for(i=m ;i>=1 ;i--)
{
sift(a,i,n);
}
for(j = n ;j>=2 ;j--)
{
tmp = a[1];
a[1] = a[j];
a[j] = tmp;
sift(a,1 ,j-1);
}
}
void main()
{
int a[]={0,7,8,3,5,2,6};
heapsort(a,6);
int i;
for(i = 1;i<=6 ;i   )
{
cout<<a[i];
}
}