排序算法部分知識點小結
…………………………………………………………………………………………………
開發工具與關鍵技術：《資料結構與算法》
作者：林敏靜
撰寫時間：2020年4月26日
…………………………………………………………………………………………………
前不久結束《資料結構與算法》的網絡課堂學習，我根據課堂學習的知識點與課後查找資料拓展知識點寫了一篇排序算法裡面的直接插入排序、快速排序與選擇排序的知識小結，如下:
- 直接插入排序：
◇基本思路：每次從無序表中取出第一個元素，把它插入到有序表的适當位置，使有序表仍然有序，每一趟都是将一個待排序記錄，按其關鍵字的大小，插入到已經排好序的一組記錄的适當位置上，直到所有待排序記錄都插入到有序段中，需要進行n-1趟。
◇直接插入算法描述：
void InsertSort(RecData
r,int n)
/*對記錄數組r[1..n]做直接插入排序*/
{int i,j;
for(i=2;i<=n;i++)
{ r[0]=r[i];/*r[i]存入監視哨r[0]*/
j=i-1;
while(r[0].key<r[j].key)
{ r[j+1]=r[j];
/*将關鍵字大于r[i].key的記錄後移*/
j--;
}
r[j+1]=r[0];/*r[i]插入到正确的位置*/
}
}/*InsertSort*/
◇效率分析：直接插入排序隻需要一個元素的輔助空間，時間複雜度為O(n2)，空間複雜度為O(1)，直接插入算法的元素移動是順序的，是穩定的算法，适用于對排序元素較少，且基本有序的資料元素排序。
- 快速排序：
◇基本思路：從待排序序列的n個記錄中任取一個記錄Ri作為基準記錄，所有關鍵字比Ri小的的元素放在Ri的前面，比Ri大的放在它後面，形成左右兩個子表，對各個子表重新選擇中心元素并依次按照規則調整（遞歸思想），直到每個子表的元素隻剩一個，此時就得到n個記錄的有序序列。
◇快速排序算法描述：
int QuickPass(RecData,int,int j)
/*對序列r[i..j]進行一趟快速排序*/
{r[0]=r[i];/*選擇第i個記錄做基準記錄*/
While(i<j)
{ while(i<j&&r[j].key>=r[0].key)
j--;/*j從右向左找小于r[0].key的記錄*/
if(i<j)
{
r[i]=r[j];/*找到小于r[0].key的記錄，交換*/
i++;
}
while(i<j&&r[i].key<r[0].key)
i++;/*i從左向右找大于r[0].key的記錄*/
if(i<j)
{ r[j]=r[i];/*找到大于r[0].key的記錄，交換*/
j--;
}
}
r[i]=r[0];
return i;
}/*QuickPass*/
◇快速排序的遞歸算法描述：
void QuickSort(RecData
r,int
l,int h)
{ int k;
if(l<h)
{
k=QuickPass(r,l,h);/*對r[l..h]劃分*/
QuickSort(r,l,k-1);/*對左區間遞歸排序*/
QuickSort(r,k+1,h);/*對右區間遞歸排序*/
}
}/*QuickSort*/
◇效率分析：快速排序算法的時間效率取決于劃分子序列的次數，對于有n個記錄的序列進行劃分，共需n-1次關鍵字的比較，在最好情況下，假設每次劃分得到兩個大緻等長的記錄子序列，時間複雜度為O(log₂n)，快速排序是一種不穩定的排序方法。
- 選擇排序：
◇基本思路：每一趟從待排序記錄中選出關鍵字最小的記錄，按順序放到已排好序的子序列中，直到全部記錄排序完畢，選擇排序有兩種：直接選擇排序和堆排序。
◇直接選擇排序的基本思路：假設待排序序列有n個記錄（R₁,R₂,…,Rn），先從n個記錄中選出關鍵字最小的記錄Rk,将該記錄與第1個記錄交換位置，完成第一趟排序，然後從剩下的n-1個記錄中再找出一個關鍵字，最小的記錄與第二個記錄交換位置，依次反複對n個記錄，經過n-1趟排序即可得到有序序列。
◇直接選擇排序算法：
void SelectSort(RecData,int n)
{ int I,j,k;
for(i=1;i<=n-1;++i)
{
k=i;
for(j=i+1;j<=n;++j)
if(r[j].key<r[k].key)/*選出關鍵字最小的記錄*/
k=j;/*k儲存目前找到的最小關鍵字的記錄位置*/
if(k!=i)
{
交換r[k]和r[i]
}
}
}/*SelectSort*/
在直接選擇排序過程中需要的關鍵字的比較次數與序列原始順序無關，當i=1時，(外循環執行第一次)，内循環比較n-1次，i=2時，内循環比較n-2次，依次類推,算法的總比較次數為(1+2+3…+n-1)=n(n-1)/2。是以,直接選擇排序的時間複雜度為O(N²)，由于隻用一個變量做輔助空間，故空間複雜度為O(1)，直接選擇排序是不穩定的。
那麼本篇文章就分享到這裡啦！若有不足的地方，還望請多多指教！