歸並排序演算法動態演示

⑴ 跪求完整一趟歸並排序演算法

#include<iomanip.h>
#include<stdlib.h>
#include<iostream.h>
#define M 11
typedef int KeyType;
typedef int ElemType;
struct rec
{
KeyType key;ElemType data;
};
typedef rec sqlist[M];
void output( sqlist r, int n )
{
for ( int i = 0; i < n; i++ )
{
cout << setw( 4 ) << r[i].key;
}
cout << endl;
}
void xuanze( sqlist b, int m, int n )
{
int i, j, k;
for ( i = m; i < n - 1; i++ )
{
k = i;
for ( j = i; j < n; j++ )
{
if ( b[k].key > b[j].key )
{
k = j;
}
}
if ( k != i )
{
rec temp = b[k];
b[k] = b[i];b[i] = temp;
}
}
}
void merge( sqlist r, int l, int m, int h, sqlist r2 )
{
xuanze( r, l, m );
xuanze( r, m, h );
output( r, M );
int i, j, k;
k = i = l;
for ( j = m; i < m && j < h; k++ )
{
if ( r[i].key <= r[j].key )
{
r2[k] = r[i];i++;
}
else
{
r2[k] = r[j];j++;
}
output( r2, M );
}
while ( j < h )
{
r2[k] = r[j];j++;k++;
}
while ( i <= m )
{
r2[k] = r[i];i++;k++;
}
output( r2, M );
}
void main()
{
cout << "guibingfa2.cpp運行結果:\n";
sqlist a, b;int i, j = 0, k = M / 2, n = M;
srand( time( 0 ) );
for ( i = 0; i < M; i++ )
{
a[i].key = rand() % 80;b[i].key = 0;
}
cout << "排序前數組:\n";
output( a, M );
cout << "數組排序的過程演示:\n";
merge( a, j, k, n, b );
cout << "排序後數組:\n";
output( b, M );cin.get();
}

⑵ 用Javascript寫排序演算法的動畫演示

1.讓JavaScript暫停下來，慢下來。
JavaScript排序是很快的，要我們肉眼能看到它的實現過程，我首先想到的是讓排序慢下來。 排序的每一個循環都讓它停300ms然後再繼續進行。 怎麼樣才能停下來呢。查了一下JavaScript貌似沒有sleep()這樣的函數。暫停做不到，但是可以想辦法讓實現跟暫停差不多的效果。比如在循環里做一些無關的事情 。
首先嘗試了讓while(true)來一直執行一個空操作。執行一段時間再回到排序邏輯。代碼大致是這樣：
for (var i = 0; i < 3; i++) {
document.writeln(i); //DOM操作
var now = new Date().getTime();
while(new Date().getTime() - now < 3000){}
}

慢是慢下來了。不過太耗資源，排序進行過程中dom並不會有任何改變，直到排序結束， DOM會變成排序好之後的樣子。 但是如果設置斷點一步步執行的時候 又可以看到一步步的排序變化。估計是因為這個操作太耗資源導致瀏覽器下達了一個DOM操作的命令但是一直騰不出資源來進行DOM操作。所以真正DOM操作的時候在js代碼執行結束之後。
所以讓JavaScript排序慢來來還是沒有實現。
另一種讓JavaScript暫停下來的思路：
寫這個文章的時候又想到一種方法來讓JavaScript停下來。 那就是AJAX的同步請求，以及超時操作。 也就是在要停下來的地方放一個AJAX請求，同步請求， 然後設置超時。超時的時間就是我們要暫停的時間。為了避免在到達超時請求之前服務 器就返回了我們的AJAX請求。可以在服務端運行類似 sleep()的程序 。從而保證AJAX不會返回。直接超時然後返回到我們的循環。不過這只是個設想。有興趣的可以去嘗試一下。
2.閉包和定時器。 這種思路不需要讓排序過程慢下來。而是使用閉包緩存排序過程中數組的變化。然後使用setTimeout來確定展示每一個數組狀態的順序。在排序循環中放入類似下面的代碼。
(function(){
var theArr = arr.slice();//當前數組狀態的備份
setTimeout(function(){
bubbleSortDom(theArr);//排序的DOM操作。
},500*timeCount);
timeCount++;//定時器的順序。
})();

不過後來發現這樣子寫的話代碼量會比較大，邏輯有修改的話要修改的地方會有點多。局限性很多，比如要實現排序動畫加快或減慢操作幾乎是很困難的。所以還要另想辦法。
3.緩存排序中的數組狀態。
也就是在排序過程中。將數組的每一輪循環的狀態保存到一個數組。然後再用這個數組依次將排序狀態保存下來。 只需要在排序中加入一句就行。
this.pushHis(arr.slice(),i-1,j,k,temp);

這樣就只需要一個setInterval()就可以了。並且可以很方便的實現動畫的加快與減慢。邏輯也比較好理解 。
問題二：如何實現JavaScript排序動畫的加快與減慢。
我們問題一使用的第三種方法。 得到一個保存了每一步排序狀態的數組arr。 然後我們可以使用一個setInterval()定時器一步步展現排序狀態。 如果要加快速度或減慢速度。就clearInterval()，修改定時器的執行間隔，重新setInterval()，從前一個定時器執行到數組中的位置開始執行。
問題三：對於使用遞歸實現的數組怎麼辦？ 不是在原數組上進行操作的怎麼辦？
使用遞歸實現的排序。 可能並沒有在一個數組上進行操作，只是最後返回一個排序好的數組出來。那麼我們要如何獲得排序中的數組的完整狀態呢。
比如快速排序。
最開始不考慮動畫，我的實現是這樣的：
function quickSort(arr){
var len = arr.length,leftArr=[],rightArr=[],tag;
if(len<2){
return arr;
}
tag = arr[0];
for(i=1;i<len;i++){
if(arr[i]<=tag){
leftArr.push(arr[i])
}else{
rightArr.push(arr[i]);
}
}
return quickSort(leftArr).concat(tag,quickSort(rightArr));
}

然後為了考慮動畫，我改寫了它的邏輯，讓它在同一個數組上進行了實現。 其實是在遞歸的時候傳入了當前的的子數組在原數組中的起始位置。從而在原數組上進行了操作。
用了兩種方法來實現方式。在排序邏輯上略有不同。
第一種是先跟遠處的對比。遇到比自己小的放到自己前面去。循環序號+1。比自己大的放到當前排序子數組的最後面去，循環序號不變。直到排列完成。
這種方法的缺點是即使是一個有序數組。它也會重新排。
第二種方法是 除了標記位，再設置一個對比位。 遇到比自己小的，放到前面去，標記位的位置+1，標記位與對比位之間所有的往後面移動一個位置。
遇到比自己大的。標記位不變，對比位+1。
這種方法的缺點是對數組進行的操作太多。優點是對有序數組不會再排。
方式一：
function quickSort(arr,a,b,qArr){

var len = arr.length,leftArr=[],rightArr=[],tag,i,k,len_l,len_r,lb,ra,temp;
if(a == undefined && b == undefined){
a = 0; b= arr.length-1;//初始化起始位置。
}
if(qArr == undefined){
qArr = arr.slice();
}

if((len == 2 && arr[0] == arr[1])||len<2){
return arr;
}

tag = qArr[a];
for (i = 1; i < len;) {
if(qArr[a+i]<=tag){
leftArr.push(qArr[a+i]);
qArr[a+i-1] = qArr[a+i];
qArr[a+i] = tag;
k = a+i;
i++;
}else{
if(leftArr.length+rightArr.length == len-1){
break;
}
temp = qArr[a+i];
qArr[a+i] = qArr[b-rightArr.length];
qArr[b-rightArr.length] = temp;
rightArr.push(temp);
k = a+i-1;
}
this.pushHis(qArr.slice(),a,b,k);
}

len_l = leftArr.length;
len_r = rightArr.length;
if(len_l== 0){
lb = a;
}else{
lb = a+len_l -1;
this.sort(leftArr,a,lb,qArr);
}

if(len_r == 0){
ra = b;
}else{
ra = b + 1 - len_r;
this.sort(rightArr,ra,b,qArr)
}
return qArr
}

方式二：
function quickSort2(arr,a,b,qArr){
var len = arr.length,leftArr=[],rightArr=[],tag,i,j,k,temp,len_l,len_r,lb,ra;
if(a == undefined && b == undefined){
a = 0; b= arr.length-1;//初始化起始位置。
}
if(qArr == undefined){
qArr = arr.slice();
}
if(len<2){
return arr;
}
if(len == 2 && arr[0] == arr[1]){
return arr;
}
tag = qArr[a];
for (i = 1,k = 0; i < len;) {
if(qArr[a+i]>=tag){
rightArr.push(qArr[a+i]);
i++;
}else{
temp = qArr[a+i];
for(j = a+i;j>a+k;j--){
qArr[j] = qArr[j-1];
// this.pushHis(qArr.slice(),a,b,a+k);
}
qArr[a+k] = temp;
leftArr.push(temp);
k++;
i++;
}
this.pushHis(qArr.slice(),a,b,a+k,i-1);
}
len_l = leftArr.length;
len_r = rightArr.length;
if(len_l== 0){
lb = a;
}else{
lb = a+len_l -1;
this.sort(leftArr,a,lb,qArr);
}
if(len_r == 0){
ra = b;
}else{
ra = b + 1 - len_r;
this.sort(rightArr,ra,b,qArr)
}
return qArr;
}

具體的不同下面會有動畫演示。
問題四：動畫的流暢。
排序動畫的DOM操作是很多的很快的。這里我做的優化只是讓每一個排序步驟只涉及一個DOM操作。 全部由JavaScript拼接好，一次替換。類似下面的代碼。
效果圖：

主要實現了：
冒泡排序JavaScript動畫演示
插入排序JavaScript動畫演示
選擇排序JavaScript動畫演示
快速排序JavaScript動畫演示
歸並排序JavaScript動畫演示
希爾排序JavaScript動畫演示

⑶ 輸入一組整數對該序列進行簡單選擇和歸並排序（數據結構用c語言寫啊）

給你一個歸並排序的具體演算法和分析：
兩路歸並排序演算法思路:
①.
把n個記錄看成n個長度為l的有序子表
;
②.
進行兩兩歸並使記錄關鍵字有序,得到n/2個長度為2的有序子表;
③.
重復第②步直到所有記錄歸並成一個長度為n的有序表為止;
具體演算法:
//
歸並操作
template
static
void
merge
(typearray[],
int
p,
int
q,
int
r){
int
i
,
k
;
int
begin1
,
end1
,
begin2
,
end2
;
int*
temp
=
(int*)malloc((r-p)*sizeof(int))
;
begin1
=
p
;
end1
=
q
;
begin2
=
q+1
;
end2
=
r
;
k
=
0
;
while
(begin1
<=
end1
&&
begin2
<=
end2){
if
(array[begin1]
<
array[begin2]){
temp[k]
=
array[begin1]
;
begin1
++
;
}
else{
temp[k]
=
array[begin2]
;
begin2
++
;
}
k
++
;
}
while
(begin1
<
end1)
temp[k++]
=
array[begin1++]
;
while
(begin2
<
end2)
temp[k++]
=
array[begin2++]
;
for
(i
=
0
;
i
<
(r-p)
;
i
++)
array[p+i]
=
temp
;
free(temp)
;
}
//--------------------------------------------------------------------------------
template
void
mergesort(typearray[],
unsigned
int
first,
unsigned
int
last){
int
mid
=
0
;
if
(first
<
last)
{
mid
=
(first+last)/2
;
mergesort
(array,
first,
mid)
;
mergesort
(array,
mid+1,
last)
;
merge
(array,
first,
mid,
last)
;
}
}

⑷ c語言的歸並排序的完整程序

這個不難:

#include<stdio.h>

// 一個遞歸函數
void mergesort(int *num,int start,int end);
// 這個函數用來將兩個排好序的數組進行合並
void merge(int *num,int start,int middle,int end);

int main()
{
// 測試數組
int num[10]= {12,54,23,67,86,45,97,32,14,65};
int i;
// 排序之前
printf("Before sorting:\n");
for (i=0; i<10; i++)
{
printf("%3d",num[i]);
}
printf("\n");
// 進行合並排序
mergesort(num,0,9);
printf("After sorting:\n");
// 排序之後
for (i=0; i<10; i++)
{
printf("%3d",num[i]);
}
printf("\n");
return 0;
}

//這個函數用來將問題細分

void mergesort(int *num,int start,int end)
{
int middle;
if(start<end)
{
middle=(start+end)/2;
// 歸並的基本思想
// 排左邊
mergesort(num,start,middle);
// 排右邊
mergesort(num,middle+1,end);
// 合並
merge(num,start,middle,end);
}
}

//這個函數用於將兩個已排好序的子序列合並

void merge(int *num,int start,int middle,int end)
{

int n1=middle-start+1;
int n2=end-middle;
// 動態分配內存，聲明兩個數組容納左右兩邊的數組
int *L=new int[n1+1];
int *R=new int[n2+1];
int i,j=0,k;

//將新建的兩個數組賦值
for (i=0; i<n1; i++)
{
*(L+i)=*(num+start+i);
}
// 哨兵元素
*(L+n1)=1000000;
for (i=0; i<n2; i++)
{
*(R+i)=*(num+middle+i+1);
}
*(R+n2)=1000000;
i=0;
// 進行合並
for (k=start; k<=end; k++)
{
if(L[i]<=R[j])
{
num[k]=L[i];
i++;
}
else
{
num[k]=R[j];
j++;
}
}
delete [] L;
delete [] R;
}

⑸ 歸並排序代碼

MERGE(rectypr R[],rectype R1[],int low,int mid,int
high)
{ int i,j,k;
i=low; j=mid+1; k=low;
while ((i<=mid)&&(j<=high))
if (R[i].key<=R[j].key) R1[k++]=R[i++];
else R1[k++]=R[j++];
while (j<=mid) R1[k++]=R[i++];
while (j<=high) R1[k++]=R[j++];
}

分析：
歸並排序就是利用上述歸並操作實現排序的。其基本思想是：將待排序列R[0]到R[n-1]看成n個長度為1的有序子序列，把這些子序列兩兩歸並，便得到high(n/2)個有序的子序列。然後再把這high(n/2)個有序的子序列兩兩歸並，如此反復，直到最後得到一個長度為n的有序序列。上述每次的歸並操作，都是將兩個子序列歸並為一個子序列，這就是「二路歸並」，類似地還可以有「三路歸並」或「多路歸並」。

一趟歸並演算法
MERGEPASS(rectype R[],rectype R1[],int length)
{ int i,j;
i=0;
while (i+2*length-1<n)
{ MERGE(R,R1,i,i+length-1,i+2*length-1);
i=i+2*length;
}
if (i+length-1<n-1)
MERGE(R,R1,i,i+length-1,n-1);
else
for (j=i;j<n;j++) R1[j]=R[j];
}

演算法復雜性分析：
歸並排序在第i 趟歸並後，有序子文件長度為2i，因此，因此，對於具有n個記錄的序列來說，必須做high(log2n)趟歸並，每趟歸並所花的時間為O(n)。所以，二路歸並排序演算法的時間復雜度為O(nlog2n)，輔助數組所需的空間為O(n)。

兩路歸並的基本思想：
設有兩個有序表A和B，對象個數分別為al和bl，變數i和j分別是兩表的當前指針。設表C是歸並後的新有序表，變數k是它的當前指針。i和j對A和B遍歷時，依次將關鍵字小的對象放到C中，當A或B遍歷結束時，將另一個表的剩餘部分照抄到新表中。

⑹ c++怎麼歸並排序

#include<cstdio>
#definemaxn700009
intn,a[maxn],temp[maxn];

voidmergesort(intl,intr)
{
	if(l==r)return;
	intmid=(l+r)>>1;
	mergesort(l,mid);mergesort(mid+1,r);//不斷分解l,r這個區間排序的大問題
	inti=l,j=mid+1,k=l;
	while(i<=mid&&j<=r)
		if(a[i]>a[j])
			temp[k++]=a[j++];
				else
					temp[k++]=a[i++];//放入一個temp數組中
	while(i<=mid)temp[k++]=a[i++];
	while(j<=r)temp[k++]=a[j++];
	for(inti=l;i<=r;i++)a[i]=temp[i];//再將temp數組反賦值回來
}

intmain()
{
	scanf("%d",&n);
	for(inti=1;i<=n;i++)
		scanf("%d",&a[i]);//讀入n個數字
	mergesort(1,n);
	for(inti=1;i<=n;i++)
		printf("%d
",a[i]);
	return0;	
}

⑺ 求快速排序演算法動畫演示，誰幫幫忙啊

http://v.youku.com/v_show/id_XMjk2NzI4OTky.html

排序演算法演示, 相信你再也找不到比這個還好的動畫演示了.

⑻ 歸並排序的演算法描述

歸並操作的工作原理如下：
第一步：申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列
第二步：設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
第三步：比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置
重復步驟3直到某一指針超出序列尾
將另一序列剩下的所有元素直接復制到合並序列尾

⑼ 歸並排序

先考慮一個簡單的問題：如何在線性的時間內將兩個有序隊列合並為一個有序隊列（並輸出）？

A隊列：1 3 5 7 9
B隊列：1 2 7 8 9

看上面的例子，AB兩個序列都是已經有序的了。在給出數據已經有序的情況下，我們會發現很多神奇的事，比如，我們將要輸出的第一個數一定來自於這兩個序列各自最前面的那個數。兩個數都是1，那麼我們隨便取出一個（比如A隊列的那個1）並輸出：

A隊列：1 3 5 7 9
B隊列：1 2 7 8 9
輸出：1

注意，我們取出了一個數，在原數列中刪除這個數。刪除操作是通過移動隊首指針實現的，否則復雜度就高了。
現在，A隊列打頭的數變成3了，B隊列的隊首仍然是1。此時，我們再比較3和1哪個大並輸出小的那個數：

A隊列：1 3 5 7 9
B隊列：1 2 7 8 9
輸出：1 1

接下來的幾步如下：

A隊列：1 3 5 7 9 A隊列：1 3 5 7 9 A隊列：1 3 5 7 9 A隊列：1 3 5 7 9
B隊列：1 2 7 8 9 ==> B隊列：1 2 7 8 9 ==> B隊列：1 2 7 8 9 ==> B隊列：1 2 7 8 9 ……
輸出：1 1 2 輸出：1 1 2 3 輸出：1 1 2 3 5 輸出：1 1 2 3 5 7

我希望你明白了這是怎麼做的。這個做法顯然是正確的，復雜度顯然是線性。

歸並排序(Merge Sort)將會用到上面所說的合並操作。給出一個數列，歸並排序利用合並操作在O(nlogn)的時間內將數列從小到大排序。歸並排序用的是分治(Divide and Conquer)的思想。首先我們把給出的數列平分為左右兩段，然後對兩段數列分別進行排序，最後用剛才的合並演算法把這兩段（已經排過序的）數列合並為一個數列。有人會問「對左右兩段數列分別排序時用的什麼排序」么？答案是：用歸並排序。也就是說，我們遞歸地把每一段數列又分成兩段進行上述操作。你不需要關心實際上是怎麼操作的，我們的程序代碼將遞歸調用該過程直到數列不能再分（只有一個數）為止。
初看這個演算法時有人會誤以為時間復雜度相當高。我們下面給出的一個圖將用非遞歸的眼光來看歸並排序的實際操作過程，供大家參考。我們可以藉助這個圖證明，歸並排序演算法的時間復雜度為O(nlogn)。

[3] [1] [4] [1] [5] [9] [2] [7]
\ / \ / \ / \ /
[1 3] [1 4] [5 9] [2 7]
\ / \ /
[1 1 3 4] [2 5 7 9]
\ /
[1 1 2 3 4 5 7 9]

上圖中的每一個「 \ / 」表示的是上文所述的線性時間合並操作。上圖用了4行來圖解歸並排序。如果有n個數，表示成上圖顯然需要O(logn)行。每一行的合並操作復雜度總和都是O(n)，那麼logn行的總復雜度為O(nlogn)。這相當於用遞歸樹的方法對歸並排序的復雜度進行了分析。假設，歸並排序的復雜度為T(n)，T(n)由兩個T(n/2)和一個關於n的線性時間組成，那麼T(n)=2*T(n/2)+O(n)。不斷展開這個式子我們可以同樣可以得到T(n)=O(nlogn)的結論，你可以自己試試。如果你能在線性的時間里把分別計算出的兩組不同數據的結果合並在一起，根據T(n)=2*T(n/2)+O(n)=O(nlogn)，那麼我們就可以構造O(nlogn)的分治演算法。這個結論後面經常用。我們將在計算幾何部分舉一大堆類似的例子。
如果你第一次見到這么詭異的演算法，你可能會對這個感興趣。分治是遞歸的一種應用。這是我們第一次接觸遞歸運算。下面說的快速排序也是用的遞歸的思想。遞歸程序的復雜度分析通常和上面一樣，主定理(Master Theory)可以簡化這個分析過程。主定理和本文內容離得太遠，我們以後也不會用它，因此我們不介紹它，大家可以自己去查。有個名詞在這里的話找學習資料將變得非常容易，我最怕的就是一個東西不知道叫什麼名字，半天找不到資料。

歸並排序有一個有趣的副產品。利用歸並排序能夠在O(nlogn)的時間里計算出給定序列里逆序對的個數。你可以用任何一種平衡二叉樹來完成這個操作，但用歸並排序統計逆序對更方便。我們討論逆序對一般是說的一個排列中的逆序對，因此這里我們假設所有數不相同。假如我們想要數1, 6, 3, 2, 5, 4中有多少個逆序對，我們首先把這個數列分為左右兩段。那麼一個逆序對只可能有三種情況：兩個數都在左邊，兩個數都在右邊，一個在左一個在右。在左右兩段分別處理完後，線性合並的過程中我們可以順便算出所有第三種情況的逆序對有多少個。換句話說，我們能在線性的時間里統計出A隊列的某個數比B隊列的某個數大有多少種情況。

A隊列：1 3 6 A隊列：1 3 6 A隊列：1 3 6 A隊列：1 3 6 A隊列：1 3 6
B隊列：2 4 5 ==> B隊列：2 4 5 ==> B隊列：2 4 5 ==> B隊列：2 4 5 ==> B隊列：2 4 5 ……
輸出： 輸出：1 輸出：1 2 輸出：1 2 3 輸出：1 2 3 4

每一次從B隊列取出一個數時，我們就知道了在A隊列中有多少個數比B隊列的這個數大，它等於A隊列現在還剩的數的個數。比如，當我們從B隊列中取出2時，我們同時知道了A隊列的3和6兩個數比2大。在合並操作中我們不斷更新A隊列中還剩幾個數，在每次從B隊列中取出一個數時把當前A隊列剩的數目加進最終答案里。這樣我們算出了所有「大的數在前一半，小的數在後一半」的情況，其餘情況下的逆序對在這之前已經被遞歸地算過了。

============================華麗的分割線============================

堆排序(Heap Sort)利用了堆(Heap)這種數據結構（什麼是堆？）。堆的插入操作是平均常數的，而刪除一個根節點需要花費O(log n)的時間。因此，完成堆排序需要線性時間建立堆（把所有元素依次插入一個堆），然後用總共O(nlogn)的時間不斷取出最小的那個數。只要堆會搞，堆排序就會搞。堆在那篇日誌里有詳細的說明，因此這里不重復說了。

============================華麗的分割線============================

快速排序(Quick Sort)也應用了遞歸的思想。我們想要把給定序列分成兩段，並對這兩段分別進行排序。一種不錯的想法是，選取一個數作為「關鍵字」，並把其它數分割為兩部分，把所有小於關鍵字的數都放在關鍵字的左邊，大於關鍵字的都放在右邊，然後遞歸地對左邊和右邊進行排序。把該區間內的所有數依次與關鍵字比較，我們就可以在線性的時間里完成分割的操作。完成分割操作有很多有技巧性的實現方法，比如最常用的一種是定義兩個指針，一個從前往後找找到比關鍵字大的，一個從後往前找到比關鍵字小的，然後兩個指針對應的元素交換位置並繼續移動指針重復剛才的過程。這只是大致的方法，具體的實現還有很多細節問題。快速排序是我們最常用的代碼之一，網上的快速排序代碼五花八門，各種語言，各種風格的都有。大家可以隨便找一個來看看，我說過了我們講演算法但不講如何實現。NOIp很簡單，很多人NOIp前就背了一個快速排序代碼就上戰場了。當時我把快速排序背完了，抓緊時間還順便背了一下歷史，免得晚上聽寫又不及格。
不像歸並排序，快速排序的時間復雜度很難計算。我們可以看到，歸並排序的復雜度最壞情況下也是O(nlogn)的，而快速排序的最壞情況是O(n^2)的。如果每一次選的關鍵字都是當前區間里最大（或最小）的數，那麼這樣將使得每一次的規模只減小一個數，這和插入排序、選擇排序等平方級排序沒有區別。這種情況不是不可能發生。如果你每次選擇關鍵字都是選擇的該區間的第一個數，而給你的數據恰好又是已經有序的，那你的快速排序就完蛋了。顯然，最好情況是每一次選的數正好就是中位數，這將把該區間平分為兩段，復雜度和前面討論的歸並排序一模一樣。根據這一點，快速排序有一些常用的優化。比如，我們經常從數列中隨機取一個數當作是關鍵字（而不是每次總是取固定位置上的數），從而盡可能避免某些特殊的數據所導致的低效。更好的做法是隨機取三個數並選擇這三個數的中位數作為關鍵字。而對三個數的隨機取值反而將花費更多的時間，因此我們的這三個數可以分別取數列的頭一個數、末一個數和正中間那個數。另外，當遞歸到了一定深度發現當前區間里的數只有幾個或十幾個時，繼續遞歸下去反而費時，不如返回插入排序後的結果。這種方法同時避免了當數字太少時遞歸操作出錯的可能。

下面我們證明，快速排序演算法的平均復雜度為O(nlogn)。不同的書上有不同的解釋方法，這里我選用演算法導論上的講法。它更有技巧性一些，更有趣一些，需要轉幾個彎才能想明白。
看一看快速排序的代碼。正如我們提到過的那種分割方法，程序在經過若干次與關鍵字的比較後才進行一次交換，因此比較的次數比交換次數更多。我們通過證明一次快速排序中元素之間的比較次數平均為O(nlogn)來說明快速排序演算法的平均復雜度。證明的關鍵在於，我們需要算出某兩個元素在整個演算法過程中進行過比較的概率。
我們舉一個例子。假如給出了1到10這10個數，第一次選擇關鍵字7將它們分成了{1,2,3,4,5,6}和{8,9,10}兩部分，遞歸左邊時我們選擇了3作為關鍵字，使得左部分又被分割為{1,2}和{4,5,6}。我們看到，數字7與其它所有數都比較過一次，這樣才能實現分割操作。同樣地，1到6這6個數都需要與3進行一次比較（除了它本身之外）。然而，3和9決不可能相互比較過，2和6也不可能進行過比較，因為第一次出現在3和9，2和6之間的關鍵字把它們分割開了。也就是說，兩個數A(i)和A(j)比較過，當且僅當第一個滿足A(i)<=x<=A(j)的關鍵字x恰好就是A(i)或A(j) （假設A(i)比A(j)小）。我們稱排序後第i小的數為Z(i)，假設i<j，那麼第一次出現在Z(i)和Z(j)之間的關鍵字恰好就是Z(i)或Z(j)的概率為2/(j-i+1)，這是因為當Z(i)和Z(j)之間還不曾有過關鍵字時，Z(i)和Z(j)處於同一個待分割的區間，不管這個區間有多大，不管遞歸到哪裡了，關鍵字的選擇總是隨機的。我們得到，Z(i)和Z(j)在一次快速排序中曾經比較過的概率為2/(j-i+1)。
現在有四個數，2,3,5,7。排序時，相鄰的兩個數肯定都被比較過，2和5、3和7都有2/3的概率被比較過，2和7之間被比較過有2/4的可能。也就是說，如果對這四個數做12次快速排序，那麼2和3、3和5、5和7之間一共比較了12*3=36次，2和5、3和7之間總共比較了8*2=16次，2和7之間平均比較了6次。那麼，12次排序中總的比較次數期望值為36+16+6=58。我們可以計算出單次的快速排序平均比較了多少次：58/12=29/6。其實，它就等於6項概率之和，1+1+1+2/3+2/3+2/4=29/6。這其實是與期望值相關的一個公式。
同樣地，如果有n個數，那麼快速排序平均需要的比較次數可以寫成下面的式子。令k=j-i，我們能夠最終得到比較次數的期望值為O(nlogn)。

這里用到了一個知識：1+1/2+1/3+...+1/n與log n增長速度相同，即∑(1/n)=Θ(log n)。它的證明放在本文的最後。

在三種O(nlogn)的排序演算法中，快速排序的理論復雜度最不理想，除了它以外今天說的另外兩種演算法都是以最壞情況O(nlogn)的復雜度進行排序。但實踐上看快速排序效率最高（不然為啥叫快速排序呢），原因在於快速排序的代碼比其它同復雜度的演算法更簡潔，常數時間更小。

快速排序也有一個有趣的副產品：快速選擇給出的一些數中第k小的數。一種簡單的方法是使用上述任一種O(nlogn)的演算法對這些數進行排序並返回排序後數組的第k個元素。快速選擇(Quick Select)演算法可以在平均O(n)的時間完成這一操作。它的最壞情況同快速排序一樣，也是O(n^2)。在每一次分割後，我們都可以知道比關鍵字小的數有多少個，從而確定了關鍵字在所有數中是第幾小的。我們假設關鍵字是第m小。如果k=m，那麼我們就找到了答案——第k小元素即該關鍵字。否則，我們遞歸地計算左邊或者右邊：當k<m時，我們遞歸地尋找左邊的元素中第k小的；當k>m時，我們遞歸地尋找右邊的元素中第k-m小的數。由於我們不考慮所有的數的順序，只需要遞歸其中的一邊，因此復雜度大大降低。復雜度平均線性，我們不再具體證了。
還有一種演算法可以在最壞O(n)的時間里找出第k小元素。那是我見過的所有演算法中最沒有實用價值的演算法。那個O(n)只有理論價值。

============================華麗的分割線============================

我們前面證明過，僅僅依靠交換相鄰元素的操作，復雜度只能達到O(n^2)。於是，人們嘗試交換距離更遠的元素。當人們發現O(nlogn)的排序演算法似乎已經是極限的時候，又是什麼制約了復雜度的下界呢？我們將要討論的是更底層的東西。我們仍然假設所有的數都不相等。
我們總是不斷在數與數之間進行比較。你可以試試，只用4次比較絕對不可能給4個數排出順序。每多進行一次比較我們就又多知道了一個大小關系，從4次比較中一共可以獲知4個大小關系。4個大小關系共有2^4=16種組合方式，而4個數的順序一共有4!=24種。也就是說，4次比較可能出現的結果數目不足以區分24種可能的順序。更一般地，給你n個數叫你排序，可能的答案共有n!個，k次比較只能區分2^k種可能，於是只有2^k>=n!時才有可能排出順序。等號兩邊取對數，於是，給n個數排序至少需要log2(n!)次。注意，我們並沒有說明一定能通過log2(n!)次比較排出順序。雖然2^5=32超過了4!，但這不足以說明5次比較一定足夠。如何用5次比較確定4個數的大小關系還需要進一步研究。第一次例外發生在n=12的時候，雖然2^29>12!，但現已證明給12個數排序最少需要30次比較。我們可以證明log(n!)的增長速度與nlogn相同，即log(n!)=Θ(nlogn)。這是排序所需要的最少的比較次數，它給出了排序復雜度的一個下界。log(n!)=Θ(nlogn)的證明也附在本文最後。
這篇日誌的第三題中證明log2(N)是最優時用到了幾乎相同的方法。那種「用天平稱出重量不同的那個球至少要稱幾次」一類題目也可以用這種方法來解決。事實上，這里有一整套的理論，它叫做資訊理論。資訊理論是由香農(Shannon)提出的。他用對數來表示信息量，用熵來表示可能的情況的隨機性，通過運算可以知道你目前得到的信息能夠怎樣影響最終結果的確定。如果我們的信息量是以2為底的，那資訊理論就變成信息學了。從根本上說，計算機的一切信息就是以2為底的信息量(bits=binary digits)，因此我們常說香農是數字通信之父。資訊理論和熱力學關系密切，比如熵的概念是直接從熱力學的熵定義引申過來的。和這個有關的東西已經嚴重偏題了，這里不說了，有興趣可以去看《資訊理論與編碼理論》。我對這個也很有興趣，半懂不懂的，很想了解更多的東西，有興趣的同志不妨加入討論。物理學真的很神奇，利用物理學可以解決很多純數學問題，我有時間的話可以舉一些例子。我他媽的為啥要選文科呢。
後面將介紹的三種排序是線性時間復雜度，因為，它們排序時根本不是通過互相比較來確定大小關系的。

附1：∑(1/n)=Θ(log n)的證明
首先我們證明，∑(1/n)=O(log n)。在式子1+1/2+1/3+1/4+1/5+...中，我們把1/3變成1/2，使得兩個1/2加起來湊成一個1；再把1/5,1/6和1/7全部變成1/4，這樣四個1/4加起來又是一個1。我們把所有1/2^k的後面2^k-1項全部擴大為1/2^k，使得這2^k個分式加起來是一個1。現在，1+1/2+...+1/n裡面產生了幾個1呢？我們只需要看小於n的數有多少個2的冪即可。顯然，經過數的擴大後原式各項總和為log n。O(logn)是∑(1/n)的復雜度上界。
然後我們證明，∑(1/n)=Ω(log n)。在式子1+1/2+1/3+1/4+1/5+...中，我們把1/3變成1/4，使得兩個1/4加起來湊成一個1/2；再把1/5,1/6和1/7全部變成1/8，這樣四個1/8加起來又是一個1/2。我們把所有1/2^k的前面2^k-1項全部縮小為1/2^k，使得這2^k個分式加起來是一個1/2。現在，1+1/2+...+1/n裡面產生了幾個1/2呢？我們只需要看小於n的數有多少個2的冪即可。顯然，經過數的縮小後原式各項總和為1/2*logn。Ω(logn)是∑(1/n)的復雜度下界。

附2：log(n!)=Θ(nlogn)的證明
首先我們證明，log(n!)=O(nlogn)。顯然n!<n^n，兩邊取對數我們得到log(n!)<log(n^n)，而log(n^n)就等於nlogn。因此，O(nlogn)是log(n!)的復雜度上界。
然後我們證明，log(n!)=Ω(nlogn)。n!=n(n-1)(n-2)(n-3)....1，把前面一半的因子全部縮小到n/2，後面一半因子全部捨去，顯然有n!>(n/2)^(n/2)。兩邊取對數，log(n!)>(n/2)log(n/2)，後者即Ω(nlogn)。因此，Ω(nlogn)是log(n!)的復雜度下界。

今天寫到這里了，大家幫忙校對哦
Matrix67原創
轉貼請註明出處

⑽ 歸並排序演算法是什麼

歸並排序演算法定義如下：

歸並排序演算法就是利用分治思想將數組分成兩個小組A，B，再將A，B小組各自分成兩個小組，依次類推，直到分出來的小組只有一個數據時，可以認為這個小組已經是有序的了，然後再合並相鄰的二個小組就可以了。這樣通過先遞歸的分解數組，再合並數組，就完成了歸並排序。

歸並排序演算法特點：

由於歸並排序在歸並過程中需要與原始記錄序列同樣數量的存儲空間存放歸並結果以及遞歸時深度為log2n(2為底)的棧空間。

因此空間復雜度為O(n+logn)，Merge函數中if(SR[i] < SR[j])語句說明需要兩兩比較，不存在跳躍，因此歸並排序是一種穩定的排序演算法，歸並排序是一種比較佔用內存，但卻效率高且穩定的演算法。