前面說了插入排序和快速排序，下面我們來看一下選擇排序。
選擇排序的基本思想是：每一趟在n-i+1的記錄中選個去關鍵字最小的記錄作為有序序列的第i個記錄。我們先來看下選擇排序中最簡單的方法，簡單選擇排序，其使用與序列元素比較少的情況。
簡單選擇排序的基本思想是，在要排序的元素序列中找到一個最小的元素，將它與序列的第一個元素進行交換，然後在剩余的n-1個元素中在找到最小的，跟剩余序列中的第一個元素進行交換，重復此過程直到全部選擇完成。
其算法思想很簡單，下面我們來看一個簡單選擇排序的小例子，進一步加深對此算法的理解：
[cpp]
#include<stdio.h>
#include<stdlib.h>
#define N 100
void Selectsort(int *arr,int n)
{
int i,j,min,t;
for(i=0;i<n-1;i++)
{
min = i;
for(j=i+1;j<n;j++)
{
if(arr[j]<arr[min])
min = j;
}
if(min-i)
{
t = arr[min];
arr[min] = arr[i];
arr[i] = t;
}
}
for(i=0;i<n;i++)
printf("L[%d]=%d\n",arr[i]);
}
int main()
{
int i,n,L[N];
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&L[i]);
Selectsort(L,n);
return 0;
}
由上面的分析可以看出，簡單選擇排序的時間復雜度為O(n2)。是不穩定的排序算法。
當數據量比較大的時候，簡單選擇排序就不太適用了，那麼我們下來看另外一種選擇排序，堆排序，其適用於大數據量的排序。
首先我們來看下什麼是堆。堆的定義是：具有n個元素的序列（h1,h2,...,hn),當且僅當滿足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)時稱之為堆。了解了堆以後，我們就來看下如何實現堆排序。(使用大跟堆)
1、先將初始初始序列L[0..n-1]建成一個大根堆，此堆為初始的無序區。
2、然後將最大的元素L[0](即堆頂)和無序區的最後一個記錄L[n-1]交換，由此得到新的無序區L[0..n-2]和有序區L[n-1]，且滿足L[0..n-2]≤L[n-1]。
3、將當前無序區L[0..n-2]調整為堆，然後再次將L[0..n-2]中最大的元素L[0]和該區間的最後一個記錄L[n-2]進行交換，這樣有得到新的無序區L[0..n-3]和有序區L[n-2..n-1]，且仍滿足關系L[0..n- 3]≤L[n-2..n-1]。
4、再將無序區調整為堆，重復以上步驟直到無序區只有一個元素為止。
前面每交換一次元素後都要重新將無序區調成為堆，那麼一個序列怎樣轉化為堆呢，下面我們來看下如何創建一個堆。
從一個無序序列建堆的過程就是一個反復篩選的過程。如將此序列看成是一個完全二叉樹，則最後一個非終端節點是第 n/2 個元素，由此篩選就從n/2開始即可。從n/2第一個非終端節點開始，比較其左右子樹的根節點，如果大於左右子樹根節點，那麼不做變動，如果小於左右子樹根節點的最大值，那麼就與這個最大值交換位置，然後繼續從n/2-1個非終端節點開始繼續比較，知道所有非終端節點比較完成，一個堆就初始化完成了。
堆排序聽起來比較復雜，那麼我們下來看一個堆排序的例子加深對堆排序的理解：
[cpp]
#include<stdio.h>
#include<stdlib.h>
#define N 100
void HeapAdjust(int *arr,int n) //建堆函數
{
int t,i,j,start,max;
start = n/2;
for(i=start;i>0;i--)
{
max = 2*i-1;
if(2*i+1<=n)
if(arr[2*i-1]<arr[2*i])
max++;
if(arr[i-1]<arr[max])
{
t = arr[max];
arr[max] = arr[i-1];
arr[i-1] = t;
}
}
t = arr[n-1]; //後面三行是將堆的根節點與最後一個元素進行交換
arr[n-1] = arr[0];
arr[0] = t;
}
void Heapsort(int *arr,int n) //堆排序函數
{
int i;
for(i=n;i>0;i--)
HeapAdjust(arr,i);
for(i=0;i<n;i++)
printf("L[%d]=%d\n",i,arr[i]);
}
int main()
{
int i,n,L[N];
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&L[i]);
Heapsort(L,n);
return 0; www.2cto.com
}
堆排序的時間復雜度是O(nln n)。是不穩定的排序算法。
以上就是對幾種基本的排序算法進行了一個大概的說明，代碼都是自己編寫，有什麼問題歡迎指正。
