資料結構面試之十——排序1（直接插入、希爾、冒泡、直接選擇排序）

題注：《面試寶典》有相關習題，但思路相對不清晰，排版有錯誤，作者對此參考相關書籍和自己觀點進行了重寫，供大家參考。

資料結構面試之十——排序1（直接插入、希爾、冒泡、直接選擇排序）

1.直接插入排序

【算法思想】：每次将一個待排序的元素，插入到前面已經排序的子序列中，直到全部元素插入完畢為止。

【算法實作】：

//最簡實作排序[交換實作].

template <class T>
void directInsertSort(T arr[],int N)
{
       inti;
       intj;
       for( i = 1; i < N; i++)
       {
              for(j= i-1; j >= 0 && arr[j+1] < arr[j];j--)
              {
                     swap(arr[j+1],arr[j]);
              }//endfor
       }//endfor
}           

//直接插入排序[移動版本]

template <class T>
void directInsertSort(T arr[], int N)
{
       inti;
       intj;
       for( i = 1; i < N; i++)
       {
              inttemp = arr[i];
              for(j = i-1; j >= 0 && temp < arr[j]; j--)
              {
                     arr[j+1]= arr[j];  //後移動
              }
              arr[j+1]= temp;        //找到插入的位置.
       }
}           

2.希爾排序

【算法思想】：将待排序的序列按照步長劃分子序列，對子序列進行直接插入排序，然後遞減步長直至為1（最小步長），這樣整個序列就會基本有序，然後進行最後一次直接插入排序即可。

template<class T>
void ShellSort(T arr[], int N)
{
       inti;
       intj;
       intstep;
       for( step = N/2; step > 0; step/=2)
       {
              for(i= step; i < N; i++) //注意此處遞增的步長為1，依次比較!
              {
                     for(j= i-step; j >=0 && arr[j+step] < arr[j]; j-=step)
                     {
                            swap(arr[j+step],arr[j]);
                     }//endfor j
              }//endfor i
       }//endfor step
}           

希爾排序，可以看做是直接插入排序的改進算法，在直接插入排序的基礎上多了外層循環，依次遞減步長，最終完成排序。

3. 冒泡排序

【算法思想】：1）将待排序的序列元素之間兩兩進行比較，如果第一個元素大于第二個元素，則進行交換；2）這樣經過一趟排序之後，確定值最大的元素在最底部；3）排序完一次後N-1，重複1），2）知道N==0為止。

//經典冒泡

template<typename T>
void BubuleSort(T a[], int N)
{
       inti,j;
       for(i= 0; i < N; i++)
       {
              for(j= 0; j < N-i-1; j++)
              {
                     if(a[j]> a[j+1])
                     {
                            swap(a[j],a[j+1]);
                     }//endif j
              }//endfor j
       }//endfor i
}           

//改進+是否交換辨別

template<typename T>
void BubuleSort(T a[], int N)
{
       inti,j;
       boolbExchange = true;         //初始設定為true
       for(i= 0; i < N && bExchange; i++)
       {
              bExchange= false;        //進入循環則設定為false
              for(j= 0; j < N-i-1; j++)
              {
                     if(a[j]> a[j+1])
                     {
                            swap(a[j],a[j+1]);
                            bExchange = true;//存在交換則變為true.
                     }//endif j
              }//endfor j
       }//endfor i
}           

4. 選擇排序

【算法思想】：同直接插入排序，将元素分為有序區和無序區。所不同的是，直接插入排序是将無序區域中第一個元素插入到有序區域以形成更大的有序區；而選擇排序是從無序區域中選擇最小的元素放入有序區的最後。

template <class T>
void SelectSort(T arr[], int N)
{
       intminPos;
       for(int i = 0; i < N; i++)
       {
              minPos= i;
              for(intj=i+1; j<N; j++)
              {
                     if(arr[j]< arr[minPos])
                     {
                            minPos= j;
                     }//endif
              }//endfor
              if(minPos!= i)
              {
                     swap(arr[minPos],arr[i]);//交換
              }
       }
}           

作者：銘毅天下

來源：CSDN

原文：

https://blog.csdn.net/laoyang360/article/details/7944448

版權聲明：本文為部落客原創文章，轉載請附上博文連結！