建站
咨詢
售后
建站咨詢
新聞中心
一、實(shí)驗(yàn)?zāi)康?/p>
掌握快速排序算法的基本思想
掌握快速排序的實(shí)現(xiàn)方法
掌握快速排序的時間性能
二、實(shí)驗(yàn)要求
熟悉C++語言編程
掌握快速排序的原理
三、實(shí)驗(yàn)內(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
四、實(shí)驗(yàn)步驟
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)查看詳情吧
網(wǎng)頁題目：快速排序?qū)嶒?yàn)（數(shù)據(jù)結(jié)構(gòu)）-創(chuàng)新互聯(lián)
本文路徑：http://ef60e0e.cn/article/jhpjs.html
