一、實驗?zāi)康?/p>

創(chuàng)新互聯(lián)主要從事網(wǎng)站設(shè)計、網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)安居,十載網(wǎng)站建設(shè)經(jīng)驗,價格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):028-86922220

掌握快速排序算法的基本思想

掌握快速排序的實現(xiàn)方法

掌握快速排序的時間性能

二、實驗要求

熟悉C++語言編程

掌握快速排序的原理

三、實驗內(nèi)容

1、問題描述

用快速排序?qū)崿F(xiàn)對無序序列的排序。

2、算法

基本思想：

任取待排序記錄序列中的某個記錄（例如取第一個記錄）作為基準(zhǔn)（樞），按照該記錄的關(guān)鍵字大小，將整個記錄序列劃分為左右兩個子序列：

左側(cè)子序列中所有記錄的關(guān)鍵字都小于或等于基準(zhǔn)記錄的關(guān)鍵字

右側(cè)子序列中所有記錄的關(guān)鍵字都大于基準(zhǔn)記錄的關(guān)鍵字

算法：

1、取序列第一個記錄為樞軸記錄，其關(guān)鍵字為Pivotkey；指針low指向序列第一個記錄位置（low=1），指針high指向序列最后一個記錄位置（High=SeqList.Len）

2、從high指向的記錄開始，向前找到第一個關(guān)鍵字的值小于Pivotkey的記錄，將其放到low指向的位置，low++

3、從low指向的記錄開始，向后找到第一個關(guān)鍵字的值大于Pivotkey的記錄，將其放到high指向的位置，high--

4、重復(fù)2、3，知道low==high，將樞軸記錄放在low（high）指向的位置

3、輸入

共一行：第一個數(shù)字n表示樣本數(shù)目，其后跟n個樣本

4、輸入樣本

8 5 6 7 9 3 4 8 2

5、輸出

第一行：原始樣本序列

第二行：第一趟快速排序結(jié)果

第三行：最終排序結(jié)果

6、輸出樣本

5 6 7 9 3 4 8 2

2 4 3 5 9 7 8 6

2 3 4 5 6 7 8 9

四、實驗步驟

1、順序表的定義

2、快速排序函數(shù)

3、順序表顯示函數(shù)

4、主函數(shù)

#define MAXLISTLEN 20 

struct List 
{
	int Key[MAXLISTLEN];
	int Len; 
}SeqList;

int FirstQuick = 'T';
void ShowSeqList();
void QuickSort(int low, int high);


int main()
{
	int i;
	
	printf("請輸入順序表的序列個數(shù)");
	scanf("%d", &SeqList.Len); 
	printf("請輸入順序表序列并以空格分隔"); 
	for(i = 1; i<= SeqList.Len; i++)
		scanf("%d", &SeqList.Key[i]);
	printf("顯示原始輸入序列\(zhòng)n"); 
	ShowSeqList();
	QuickSort(1, SeqList.Len);
	printf("顯示最終排序結(jié)果:\n ");
	ShowSeqList();
	return 1;
}
//顯示順序表顯示函數(shù)
void ShowSeqList()
{
	int i;
	for(i = 1; i< SeqList.Len; i++)
		printf("%d ", SeqList.Key[i]);
	printf("%d\n", SeqList.Key[i]);	
}

void QuickSort(int low, int high)
{
	int i, j, Pivotkey;
	i = low; 
	j = high;
	Pivotkey = SeqList.Key[low];  //記錄順序表的上、下界
	
	
	while(i< j)
	{
		// 當(dāng)high>low的時候循環(huán)
		while(i< j && SeqList.Key[j] >= Pivotkey)
		{
			j--;
		}
		if(i< j)
			SeqList.Key[i++] = SeqList.Key[j];
		//將比基準(zhǔn)小的數(shù)扔向前面
		while(i< j && SeqList.Key[i]< Pivotkey)      
        {
            i++;
        }

        if(i< j)
        {
            SeqList.Key[j--] = SeqList.Key[i];
        }
	}
	SeqList.Key[i] = Pivotkey; 	
	 //顯示第一趟快速排序結(jié)果
	if(FirstQuick == 'T') 
	{
		printf("顯示第一次排序結(jié)果\n");	
		ShowSeqList();
	}	
	FirstQuick = 'F';
  //對子序列數(shù)組進(jìn)行遞歸快速排序
	if(low< i - 1)QuickSort(low , i- 1);	
	if(j +1< high)QuickSort(j + 1, high);
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

標(biāo)題名稱：快速排序?qū)嶒灒〝?shù)據(jù)結(jié)構(gòu)）-創(chuàng)新互聯(lián)
文章分享：http://weahome.cn/article/jhpjs.html