資料結構：内排序（C++）

一、插入排序

基本思想：

逐個處理待排序的記錄。每個新記錄與前面已排序的子序列進行比較，将它插入到子序列中正确的位置。

排序過程：

（1）輸入一個記錄數組A，存放着n條記錄。

（2）先将數組中第1個記錄看成是一個有序的子序列，然後從第2個記錄開始，依次逐個進行處理(插入)将第i個記錄X，依次與前面的第i-1個、第i-2個，…，第1個記錄進行比較，每次比較時，如果X的值小，則交換，直至遇到一個小于或等于X的關鍵碼，或者記錄X已經被交換到數組的第一個位置，本次插入才完成。

（3）繼續處理，直至最後一個記錄插入完畢，整個數如中從元表将按關鍵碼非遞減有序排列。

僞代碼描述：

template <class Elem, class Comp>
void inssort (Elem A[], int n)
{
	for (int i=1; i<n; i++)
	for (int j=i; (j>0) && (Comp::prior(A[j]，A[j-1])); j--)
	swap(A, j, j-1) ;
}
           

加入監視哨的插入排序僞代碼描述：

template <class Elem, class Comp>
void inssort (Elem A[], int n)
{
	for (int i=1; i<n; i++)
	{int value = A[i];
	j = i-1;
	while (Comp::prior(value, A[j]))
		{A[j+1] = A[j];
		j--;
		}
	A[j+1] = value;
	}
}
           

二、冒泡排序

基本思想：

比較并交換相鄰元素對,直到所有元素都被放到正确的地方為止。

排序過程：

（1）輸入一個記錄數組A，存放着n條記錄。

（2）每次都從數組的底部( 存放最後一個記錄)開始，将第n-1個位置的值與第n-2個位置的值比較，若為逆序，則交換兩個位置的值，然後，比較第n-2個位置和第n-3個位置的值，依次處理，直至第2個位置和第1個位置值的比較(交換)。

（3）重複這個過程n-1次，整個數組中的元素将按關鍵碼非遞減有序排列。

僞代碼描述：

template <class Elem, class Comp>
void bubsort (Elem A[], int n)
{
	for (int i=0; i<n-1; i++)
	for (int j=n-1; j>i; j--)
	if(Comp::prior(A[j], A[j-1]))
	swap(A, j, j-1) ;
}
           

改進後的冒泡排序僞代碼描述：

template <class Elem, class Comp>
void bubsort (Elem A[], int n)
{
	bool flag；
	for (int i=0; i<n-1; i++)
	{flag = false；
	for (int j=n-1; j>i; j--)
	if(Comp::prior(A[j], A[j-1]))
		{swap(A, j, j-1);
		flag = true;
		}
	if(flag==flase) return;//發現已全部有序了
	}
}
           

三、選擇排序

基本思想：

第i次時“選擇”序列中第i小的記錄，并把該記錄放到序列的第i個位置上。

排序過程：

（1）輸入一個記錄數組A，存放着n條記錄。

（2）對于n個記錄的數組，共進行n-1趟排序。

每一趟在n-i+1個(i=1,2, … n-1)記錄中通過n-i次關鍵字的比較選出關鍵碼最小的記錄和第i個記錄進行交換

（3）經過n-1趟，整個數組中的元素将按關鍵碼非遞減有序排列。

僞代碼描述：

template <class Elem, class Comp>
void selsort (Elem A[], int n)
{
	for (int i=0; i<n-1; i++)
	{int lowindex = i; // Remember its index
	for (int j=n-1; j>i; j--) // Find least
	if (Comp::prior(A[j], A[lowindex]))
		lowindex= j; // Put it in place
	swap(A, i, lowindex);
	}
}
           

四、希爾排序

動機：

插入排序算法簡單，在n值較小時，效率比較高；在n值很大時，若序列按關鍵碼基本有序，效率依然較高，其時間效率可提高到O(n)。

基本思想:

先将整個待排記錄序列分割成若千個較小的子序列，對子序列分别進行插入排序，然後把有序子序列組合起來;待整個序列中的記錄“基本有序”時,再對全體記錄進行一次插入排序。

排序過程：

（1）輸入一個記錄數組A，存放着n條記錄以及一個(遞

減)增量序列數組

（2）按照遞減的次序，對于每一個增量，從數組的位置1開始，根據增量計算出子序列的最後一個值的位置，然後調用基于增量的插入排序函數；從數組的位置2開始，根據增量計算出子序列的最後一個值的位置，然後調用基于增量的插入排序函數；依次類推，計算出目前增量下的所有子序列，并排序。

（3）依法處理下一個增量，直至增量為1，執行一次标準的簡單插入排序。

基于增量的插入排序過程：

（1）輸入一個記錄數組A，起始位置i，結束位置n，增量incr

（2）先将數組中第i位置的記錄看成是一個有序的子序列，然後從第i+jincr位置的記錄開始，依次對逐個增量位置進行處理(插入)将第i+jincr位置的記錄X，依次與前面的第i+(j-1)*incr位置、第i+(j-2)*incr位 置，.，. 第i位 置的記錄進行比較，每次比較時，如果X的值小，則交換，直至遇到一個小于或等于X的關鍵碼，或者記錄X已經被交換到第i位置，本次插入才完成。

（3）繼續處理，直至最後一個記錄插入完畢，整個子序列有序。

僞代碼描述：

template <class Elem, class Comp>
void inssort2(Elem A[], int n, int incr)
{
	//子序列插入排序
	for (int i=incr; i<n; i+=incr)
	for (int j=i; (j>=incr) && (Comp::prior(A[j], A[j-incrI]); j-=incr)
	swap(A, j, j-incr);
}

template <class Elem, class Comp>
void shellsort(Elem A[], int n)
{
	for (int i=n/2; i>2; i/=2) // For each incr
	for (int j=0; j<i; j++) // Sort sublists
	inssort2<E,Comp>(&A[j], n-j, i);
	inssort2<E,Comp>(A, n, 1);
}
           

五、歸并排序

動機：分治思想

基本思想：将兩個或多個有序表歸并成一個有序表

2路歸并排序基本思想：

（1）設有n個待排記錄，初始時将它們分為n個長度為1的有序子表；

（2）兩兩歸并相鄰有序子表，得到若千個長度2為的有序子表；

（3）重複（2） 直至得到一個長度為n的有序表。

排序過程:

歸并排序(劃分過程)用遞歸實作。

（1）若目前(未排序)序列的長度不大于1，則傳回目前序列；

（2）否則，将目前未排序序列分割為大小相等的兩個子序列，分别用歸并排序對兩個子序列進行排序，将傳回的兩個有序子序列合并成一個有序序列。

合并兩個有序子序列的過程：

（1）記錄數組A，起始位置left，結束位置right，中間點mid；

（2）首先将兩個子序列複制到輔助數組中，

首先對輔助數組中兩個子序列的第一條記錄進行比較，并把較小的記錄作為合并數組中的第一個記錄，複制到原數組的第一個位置上；

繼續使用這種方法，不斷比較兩個序列中未被處理的記錄，并把結果較小的記錄依次放到合并數組中，直到兩個序列的全部記錄處理完畢。

（3）注意要檢查兩個子序列中的一個被處理完，另一個未處理完的情況。隻需依次複制未處理完的記錄即可。

僞代碼描述：

template <class Elem, class Comp>
void mergesort(E A[], Elem temp[], int left, int right)
{
	if (left == right) return;
	int mid = (left+right)/2;
	mergesort<E,Comp>(A, temp, left, mid);
	mergesort<E,Comp>(A, temp, mid+1, right);
	for (int i=left; i<=right; i++) // Copy
	temp[i] = A[i];
	int i1 = left; int i2= mid+ 1;
	for (int curr=left; curr<=right; curr++)
	{if(i1 == mid+1)
	// Left exhausted
		A[curr] = temp[i2++];
	else if (i2 > right) // Right exhausted
		A[curr] = temp[i1++];
	else if (Comp::prior(temp[i1], temp[i2]))
		A[curr] = temp[i1++];
	else
		A[curr]= temp[i2++];
	}
}
           

優化歸并排序算法僞代碼描述：

template <class Elem, class Comp>
void mergesort(Elem A[], E temp[],int left, int right)
{
	if (right-left) <= THRESHOLD)
	{inssort<E,Comp>(&A[left],right-left+1);
	return;
	}
	int i, j, k, mid = (left+right)/2;
	if (left == right) return;
	mergesort<E,Comp>(A, temp, left, mid);
	mergesort<E,Comp>(A, temp, mid+1, right);
	for (i=mid; i>=left; i--) templil = A[i];//正序複制前半個表
	for (i=1; j<=right-mid; j++)
	temp[right-j+1] = A[j+mid];//逆序複制後半個表
	for (i=left,j=right,k=left; k<=right; k++)// 從前後兩半個表相向比較來複制較小值
	if(temp[i] < templi)
		A[k] = temp[i++];
	else
		A[k] = templ[j--];
}
           

六、快速排序

動機：

分治思想:劃分交換排序

基本思想：

在待排序記錄中選取一-個記錄R(稱為軸值pivot)，通過一趟排序将其餘待排記錄分割(劃分)成獨立的兩部分，比R小的記錄放在R之前，比R大的記錄放在R之後，然後分别對R前後兩部分記錄繼續進行同樣的劃分交換排序，直至待排序序列長度等于1，這時整個序列有序。

排序過程：

快速排序(劃分過程)用遞歸實作。

（1）若目前(未排序)序列的長度不大于1，則傳回目前序列；

（2）否則在待排序記錄中選取一個記錄做為軸值，通過劃分算法将其餘待排記錄劃分成兩部分，比R小的記錄放在R之前，比R大的記錄放在R之後；分别用快速排序對前後兩個子序列進行排序(注意軸值已經在最終排序好的數組中的位置。無須繼續處理)

選取軸值，劃分序列的過程：

（1）記錄數組A，待排子序列左、右兩端的下标i和j；

（2）選取待排序子序列中間位置的記錄為軸值，交換軸值和位置j的值，依據在位置j的軸值，将數組i-1到j之 間的待排序記錄劃分為兩個部分(i到k-1之 間的記錄比軸值小，k到j-1之間的記錄比軸值大)；

（3）從數組i-1到j之間的待排序序列兩端向中間移動下标，必要時交換記錄，直到兩端的下标相遇為止(相遇的位置記為k)，交換軸值和位置k的值。

僞代碼描述：

template < class Elem, class Comp >
void qsort(Elem A[], int i, int j)
{
	if(j <= i) return; // List too small
	int pivotindex = findpivot(A, i, j);
	swap(A, pivotindex, j); // Put pivot at end k will be first position on right side
	int k = partition<E,Comp>(A,i-1, j, A[j]);
	swap(A, k, j);
	// Put pivot in place
	qsort<E,Comp>(A, i, k-1);
	qsort<E,Comp>(A, k+1, j);
}

template <class E1em>
int findpivot (E1em A[], int i, int j)
{
	return (i+j) /2;
}

template < typename E, typename Comp >
inline int partition(E A[], int l, int r, E& pivot)
{
	do
	{//Move the bounds inward until they meet
	// Move l right and
	while(Comp::prior (A[++l], pivot));
	while((l < r) && Comp::prior(pivot, A[--r])); // r left
	swap(A, l, r) ; //Swap out-of- place values
	} while (l < r) ; // Stop when they cross
	return l; //Return first position in right part
}
           

七、堆排序

動機：

選擇排序：樹形選擇排序，最值堆

基本思想:

首先将數組轉化為一個滿足堆定義的序列。然後将堆頂的最值取出，再将剩下的數排成堆，再取堆頂數值，…，如此下去，直到堆為空，就可得到一個有序序列。

排序過程：

（1）建堆：将輸入序列用數組存儲，利用堆的建構函數将數組轉化為一個滿足堆定義的序列(如果是遞增排序，則建構最大值堆，反之，建構最小值堆)

（2）然後将堆頂的最大元素取出，再将剩下的數排成堆，再取堆頂數值，…，如此下去，直到堆為空。每次應将堆頂的最大元素取出放到數組的最後。

（3）假設n個元素存于數組中的0到n-1位置上。把堆頂元素取出時，應該将它置于數組的第n-1個位置。這時堆中元素的數目為n-1個。再按照堆的定義重新排列堆，取出最大值并放入數組的第n-2個位置。到最後結束時，就排出了一個由小到大排列的數組。

僞代碼描述：

template< Kclass Elem, class Comp>
void heapsort (Elem A[], int n)
{
	Elem mval ;
	maxheap KElem,Comp> H(A, n, n) ;
	for (int i=0; i<n; i++)	// Now sort
	H. removemax (mval) ; // Put max at end
}
           

八、配置設定排序

動機：

配置設定：按關鍵碼劃分；不進行關鍵碼比較。

基本思想：

關鍵碼用來确定一個記錄在排序中的最終位置。

僞代碼描述：

for (i=0; i<n; i++)
B[A[i]] = A[i] ;

template <class E, class getkey>
void binsort(E A[], int n)
{
	List<E> B[MaxKeyValue] ;
	E item;
	for (i=0; i<n; i++)
	B[A[i]].append (getkey::A[i]));
	for (i=0; i<MaxKeyValue; i++)
	for (B[i].setStart() ;
	B[i].getValue(item); B[i].next() )
	output(item) ;
}
           

桶式排序(bucket sort)：

分治法:

（1）将序列中的元素配置設定到一組(數量有限的)桶中；

（2）每個桶再分别排序(可以使用其它排序方法或遞歸使用桶式排序)；

（3）最後，依序周遊每個桶，将所有元素有序放回序列。

九、基數排序

動機：

配置設定排序：按關鍵碼劃分；不進行關鍵碼比較；而是一種多關鍵字的排序

基本思想：

将關鍵碼看成有若千個關鍵字複合而成。然後對每個關鍵字進行配置設定(計數)排序依次重複，最終得到一個有序序列。

排序過程：

（1）将所有待排序數值(正整數)按照基數r統一為同樣的數位長度，數位較短的數前面補零。

（2）然後，從最低位開始，依次進行每趟(計數配置設定)排序。定義一個長度為r的輔助數組cnt。記錄每個盒子裡有多少個元素。初始值為0。定義一個和原數組A一樣大小的數組B。依次處理每個元素，根據元素的值計算其盒子編号，統計出每個盒子需要存放的記錄數。(cnt[j]存儲了數位j (第i個盒子)在這一趟排序時配置設定的記錄數)

（3）利用cnt的值，計算該盒子在數組B中的( 最後一個)下标位置，從後向前，依次把數組A中的元素，依據該元素在cnt中記錄的下标，把元素值存入(配置設定)數組B的(盒子中)相應位置将數組B的值依次複制到數組A，進行下一趟排序。

僞代碼描述：

template <class E1em, class Comp>
void radix (Elem A[], Elem B[], int n, int k, int r, int cnt[]){
	// cnt[i] stores # of records in bin[i]
	int j;
	for (int i=0，rtok= =1; i<k; i++, rtok*=r) {
	for (j=0; j<r; j++) cnt[j] = 0;
	// Count # of records for each bin
	for(j=0; j<n; j++) cnt[(A[j]/rtok)%r]++;
	// cnt[j] will be last slot of bin j .
	for (j=1; j<r; j++)
	cnt[j] = cnt[j-1] + cnt[j] ;
	for (j=n-1; j>=0; j--)
	B[--cnt[(A[j]/rtok)%r]] = A[j] ;
	for (j=0; j<n; j++)
	A[j] = B[j] ;
	}
}
           

十、性能比較及總結

性能比較

總結

（1）簡單排序以直接插入排序最簡單，當序列“基本有序”或n較小時，它是最佳排序方法，通常用它與先進的排序方法結合使用。如果記錄空間大，宜用移動次數較少的簡單選擇排序。

（2）平均時間性能快速排序最佳，但最壞情況下的時間性能不如堆排序和歸并排序。

（3）基數排序最适合n很大而關鍵字較小的序列。

（4）從穩定性看,歸并排序,基數排序插入排序和冒泡排序是穩定的；而選擇排序、快速排序、堆排序和希爾排序是不穩定的。

（5）簡單排序，堆排序和快速排序對記憶體占用小；而歸并排序和各種配置設定排序需要輔助空間。