程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> C語言快速排序算法代碼分析

C語言快速排序算法代碼分析

編輯:關於C語言

首先,要對快速排序的原理有一定的了解,先看C語言快速排序的代碼。

void sort(int a[],int size)
{
	int i=0,j=size-1,value=a[0];
	if(size>1)
	{
		while(ivalue)
				{
					a[j]=a[i];
					break;
				}
			}
		}

		a[i]=value;
		sort(a,i);
		sort(&a[i+1],size-i-1);
	}
}

分析內部循環:

while(ivalue)
		{
			a[j]=a[i];
			break;
		}
	}
}

這個循環的作用是:把小的數都放在左端,大的數都放在右端。
現在假設初始值是:6 9 7 3 4,j=4, i=0,以6為對比值,把小於6的放在數據6的左邊,大於6的放在6的右邊,看下圖,


把6(也就是a[0]的值)當作對比值,當執行第一次循環體的時候:

(第一個for循環)從右向左找比6小的,初始值中6 9 7 3 4,可以發現4比6小,於是把4賦給a[0],或許有的朋友會疑惑,a[0]的值那不就被覆蓋了麼,其實剛開始6已經賦值給value了,大家根據代碼也可以發現。 於是原來的值等於4的位置,也就是a[4](上圖第三行的黃底顯示),這就是一個“坑位”,裡面好像是保存了數據,但是這個數據沒用,因為它的值已經保存到了a[0](原a[0]的值保存到了value)。此時數組的元素為 4 9 7 3 4

(第二個for循環)從左向右找比6大的,根據上一個執行結果數組的元素改變為 4 9 7 3 4,9比6大,就是把9裝到上面那個坑位中。這個9原來所在的地方,也就是a[1]於是空了出來(盡管它裡面有個沒用的數據),成為坑位。

循環體執行一次成功。

接下來執行,第二次循環。到最後,最後的坑位是a[2]。


這個while循環體,執行完之後,i就會等於j。這個地方值得大家注意一下。而且i==2,剛好是坑位所在的位置。當執行完循環體後,a[2]=value;

發現沒,此時數組元素 4 3 6 7 9,以6為分節點,這個循環成功的完成他的任務。


接下來就是把4 3 看作新數組,7 9看作新數組。接著遞歸下去,直到這樣分割到只剩一個元素為止。


小學生能力有限,請大神幫忙斧正。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved