【快速排序】—— [USACO07DEC]Bookshelf B
- 快速排序方法
- 背景
- 方法的簡單介紹
- 圖解快速排序
- C語言代碼實作
- 用二分法改進快速排序
- 例題分析
快速排序方法
背景
快速排序（Quicksort）是對冒泡排序的一種改進，它由C. A. R. Hoare在1960年提出，其基本思想是：通過一趟排序將要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然后再按此方法對這兩部分資料分別進行快速排序，整個排序程序可以遞回進行，以此達到整個資料變成有序序列，這種方法既不浪費空間，又可以快速地排序，
方法的簡單介紹
例如對 a[10] = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8} 進行排序，首先我們要在這個序列中隨便找一個數作為基準數，以 “6” 為例作基準數
temp = a[0];
6 1 2 7 9 3 4 5 10 8
^
我們需要做的是把比 6 小的數移到左邊，比 6 大的數移到右邊，有什么辦法能做到這點嗎？
我們分別從序列的兩端開始“探測”， 左端標記為 i ， 右端標記為 j
6 1 2 7 9 3 4 5 10 8
^ ^
i j
因為所設定的基準數是最左邊的數，所以 j 先開始一步一步向左移動,直到找到比基準數 temp 小的數時停下（注意要保證 j 在 i 右邊）
while(a[j] >= temp && j > i)
j--;
接下來向右移動i，當i遇到比基準數temp大的數時停下
while(a[i] >= temp && j > i)
i++;
此時 i ，j 位置如下
6 1 2 7 9 3 4 5 10 8
^ ^
i j
下一步，交換 a[i] 和 a[j]
6 1 2 5 9 3 4 7 10 8
^ ^
i j
到此，第一次交換結束，接下來進行第二次交換（每次都是 j 先移動)
6 1 2 5 9 3 4 7 10 8
^ ^
i j
交換 a[i]和 a[j]
6 1 2 5 4 3 9 7 10 8
^ ^
i j
當進行第三次交換時，j 停在了 “3” 的位置，而 i 向右移動會與 j 相遇
當他們相遇時，我們將基準數temp與 “3” 交換
3 1 2 5 4 6 9 7 10 8
^ ^
到此第一輪 “探測” 結束我們發現比基準數小的數都移到了左邊，比基準數大的數都移到了右邊，
不過我們發現 “6” 左右兩邊的序列還是混亂的，
接下來只要模擬剛才的方法，分別處理6左邊的序列和右邊的序列即可，
例如對左邊的序列
3 1 2 5 4
我們可以以 “3” 為基準數進行“探測”，當 “3” 歸位時再處理 “3” 左右兩邊的序列，直到無法拆分出新的子序列，
最終序列即為
1 2 3 4 5 6 7 8 9 10
圖解快速排序
C語言代碼實作
#include <stdio.h>
#include <stdlib.h>
int a[100000], n;
void QuickSort(int left, int right)
{
int i,j,t,temp;
if(left<=right)
{
temp = a[left]; /* 定義基準數 */
i = left;
j = right;
while(i != j)
{
/* 將j向左移動 */
while(a[j]>=temp && i<j)
j--;
/* 將i向右移動 */
while(a[i]<=temp && i<j)
i++;
if(i < j) //***********************//
{ // 若i與j沒有相遇 //
t = a[i]; // 交換i與j指向的數 //
a[i] = a[j]; //**********************//
a[j] = t;
}
}
a[left] = a[i];
a[i] = temp;
QuickSort(left, i-1); /* 遞回處理左邊的序列 */
QuickSort(i+1, right); /* 遞回處理右邊的序列 */
}
}
int main()
{
/* 讀入資料 */
scanf("%d", &n);
for(int i=0; i<n; i++)
scanf("%d", a+i);
/* 排序 */
QuickSort(0, n-1);
/* 輸出 */
for(int i=0; i<n; i++)
printf("%d ", a[i]);
return 0;
}
用二分法改進快速排序
用二分法的思想，把中間數作為基準數，因此QuickSort函式可改為如下形式：
void QuickSort(int left, int right)
{
int i,j,t,temp;
if(left<right)
{
temp = a[(left+right)/2]; /* 定義中間數為基準數 */
i = left;
j = right;
while(i <= j)
{
/* 將i向右移動 */
while(a[i] < temp)
i++;
/* 將j向左移動 */
while(a[j] > temp)
j--;
if(i <= j)
{ //***********************//
t = a[i]; // 交換i與j指向的數 //
a[i++] = a[j]; //***********************//
a[j--] = t;
}
}
if(left<j) QuickSort(left, j); /* 遞回處理左邊的序列 */
if(i<right) QuickSort(i, right); /* 遞回處理右邊的序列 */
}
}
例題分析
下面來看一道有關快速排序的題吧
[USACO07DEC]Bookshelf B
-
題目描述
Farmer John最近為奶牛們的圖書館添置了一個巨大的書架，盡管它是如此的大，但它還是幾乎瞬間就被各種各樣的書塞滿了，現在，只有書架的頂上還留有一點空間，
所有N(1 <= N <= 20,000)頭奶牛都有一個確定的身高H_i(1 <= H_i <= 10,000)，設所有奶牛身高的和為S，書架的高度為B，并且保證 1 <= B <= S < 2,000,000,007，
為了夠到比最高的那頭奶牛還要高的書架頂，奶牛們不得不像演雜技一般，一頭站在另一頭的背上，疊成一座“奶牛塔”，當然，這個塔的高度，就是塔中所有奶牛的身高之和，為了往書架頂上放東西，所有奶牛的身高和必須不小于書架的高度，
顯然，塔中的奶牛數目越多，整座塔就越不穩定，于是奶牛們希望在能夠到書架頂的前提下，讓塔中奶牛的數目盡量少， 現在，奶牛們找到了你，希望你幫她們計算這個最小的數目， -
輸入格式
第1行: 2個用空格隔開的整數：N 和 B * 第2…N+1行: 第i+1行是1個整數：H_i -
輸出格式
第1行: 輸出1個整數，即最少要多少頭奶牛疊成塔，才能夠到書架頂部 -
輸入輸出樣例
-
輸入 #1
6 40
6
18
11
13
19
11 -
輸出 #1
3
-
-
說明/提示
-
輸入說明:
一共有6頭奶牛，書架的高度為40，奶牛們的身高在6~19之間，
-
輸出說明:
一種只用3頭奶牛就達到高度40的方法：18+11+13，當然還有其他方法，在此不一一列出了，
-
-
代碼實作
#include <stdio.h>
#include <stdlib.h>
int a[200000], n;
void QuickSort(int left, int right)
{
int i,j,t,temp;
if(left<right)
{
temp = a[(left+right)/2]; /* 定義中間數為基準數 */
i = left;
j = right;
while(i <= j)
{
/* 將i向右移動 */
while(a[i] < temp)
i++;
/* 將j向左移動 */
while(a[j] > temp)
j--;
if(i <= j)
{ //***********************//
t = a[i]; // 交換i與j指向的數 //
a[i++] = a[j]; //***********************//
a[j--] = t;
}
}
if(left<j) QuickSort(left, j); /* 遞回處理左邊的序列 */
if(i<right) QuickSort(i, right); /* 遞回處理右邊的序列 */
}
}
int main()
{
int i, max, sum=0;
/* 讀入資料 */
scanf("%d%d", &n, &max);
for(i=0; i<n; i++)
{
scanf("%d", a+i);
}
/* 排序 */
QuickSort(0, n-1);
for(i=n-1; i>=0; i--)
{
sum += a[i];
if(sum >= max)
break;
}
/* 輸出 */
printf("%d", n-i);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/236638.html
標籤：其他
下一篇：javax.imageio.IIOException: Can‘t create output stream!（驗證碼圖片不顯示）