快速排序（quick sort）是冒泡排序改進(jìn)而來的题诵，基本思想是在待排序的n個(gè)元素中襟企，取第一個(gè)元素作為基準(zhǔn)，將該元素放在適當(dāng)?shù)奈恢梅那遥瑢⑦@個(gè)數(shù)據(jù)序列分為兩部分帮坚，到這里稱為一趟排序妻往。此時(shí)基準(zhǔn)數(shù)左邊的數(shù)都比它小，基準(zhǔn)數(shù)右邊的數(shù)都比大试和。接下來便用同樣的方法分別對(duì)左右兩邊的數(shù)據(jù)進(jìn)行排序讯泣，直到序列中沒有元素或只有一個(gè)元素。
快速排序每趟僅將一個(gè)元素歸位阅悍。
接下來看一趟劃分的代碼好渠，原理就是設(shè)置兩個(gè)指示器i和j分別指向序列的第一個(gè)和最后一個(gè)元素。先是j從右往左掃描节视，當(dāng)掃描到比基數(shù)小的元素就將該元素賦值到i指向的元素拳锚。然后便拍到i從左往右掃，當(dāng)掃描到比基數(shù)大的元素就將該元素賦值給j指向的元素肴茄。如此循環(huán)直到i和j相遇晌畅，便將基數(shù)賦值給兩個(gè)指針同時(shí)指向的這個(gè)元素。此時(shí)便是一趟排序完成寡痰。
一趟劃分
int partition(int R[], int s, int t)//一趟劃分
{
int i = s, j = t;
int tmp = R[i];//以第一個(gè)數(shù)為基準(zhǔn)
while (i<j)//兩端交替向中間掃描，直到i=j為止
{
while (j>i&&R[j]>=tmp)//從右向左掃描
{
j--;
}
R[i] = R[j];//右邊掃描結(jié)束
while (i<j&&R[i]<=tmp)
{
i++;
}
R[j] = R[i];//左邊掃描結(jié)束
}
R[i] = tmp;
//輸出每趟劃分后的序列
for (int i = 0; i <= 6; i++)
{
cout << R[i]<<" ";
}
cout << endl;
return i;
}
快讀排序其實(shí)是一個(gè)遞歸的過程棋凳，遞歸出口為當(dāng)序列中沒有元素或只有一個(gè)元素拦坠。下面的代碼便是遞歸先對(duì)左區(qū)間序列進(jìn)行排序，再對(duì)右區(qū)間序列進(jìn)行排序剩岳。
遞歸調(diào)用
void QuickSort(int R[], int s, int t)
{
int i;
if (s < t)//區(qū)間內(nèi)至少存在兩個(gè)元素的情況
{
i = partition(R, s, t);
QuickSort(R, s, i - 1);//對(duì)左區(qū)間遞歸排序贞滨，二趟排序
QuickSort(R, i + 1, t);//對(duì)右區(qū)間遞歸排序，三趟排序
}
}
最后我們可以隨便給一個(gè)數(shù)組進(jìn)行排序測(cè)試
int main()
{
int R[] = { 6,10,10,3,7,1,8 };
QuickSort(R, 0, 6);//后面兩個(gè)參數(shù)為下標(biāo)
return 0;
}
完整代碼如下
#include <iostream>
using namespace std;
int partition(int R[], int s, int t)//一趟劃分
{
int i = s, j = t;
int tmp = R[i];//以第一個(gè)數(shù)為基準(zhǔn)
while (i<j)//兩端交替向中間掃描拍棕，直到i=j為止
{
while (j>i&&R[j]>=tmp)//從右向左掃描
{
j--;
}
R[i] = R[j];//右邊掃描結(jié)束
while (i<j&&R[i]<=tmp)
{
i++;
}
R[j] = R[i];//左邊掃描結(jié)束
}
R[i] = tmp;
//輸出每趟劃分后的序列
for (int i = 0; i <= 6; i++)
{
cout << R[i]<<" ";
}
cout << endl;
return i;
}
void QuickSort(int R[], int s, int t)
{
int i;
if (s < t)//區(qū)間內(nèi)至少存在兩個(gè)元素的情況
{
i = partition(R, s, t);
QuickSort(R, s, i - 1);//對(duì)左區(qū)間遞歸排序晓铆，二趟排序
QuickSort(R, i + 1, t);//對(duì)右區(qū)間遞歸排序，三趟排序
}
}
int main()
{
int R[] = { 6,10,10,3,7,1,8 };
QuickSort(R, 0, 6);//后面兩個(gè)參數(shù)為下標(biāo)
return 0;
}
最終輸出采用快速排序后4趟排序結(jié)果
image.png
