快速排序方法

A. 快速排序演算法和西爾排序

快速排序（Quicksort）是對冒泡排序的一種改進。由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
演算法過程:
設要排序的數組是A[0]……A[N-1]，首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然後將所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序。一趟快速排序的演算法是：
1）設置兩個變數I、J，排序開始的時候：I=0，J=N-1；
2）以第一個數組元素作為關鍵數據，賦值給key，即 key=A[0]；
3）從J開始向前搜索，即由後開始向前搜索（J=J-1），找到第一個小於key的值A[J]，並與A[I]交換；
4）從I開始向後搜索，即由前開始向後搜索（I=I+1），找到第一個大於key的A[I]，與A[J]交換；
5）重復第3、4、5步，直到 I=J； (3,4步是在程序中沒找到時候j=j-1，i=i+1，直至找到為止。找到並交換的時候i， j指針位置不變。另外當i=j這過程一定正好是i+或j-完成的最後另循環結束)
例如：待排序的數組A的值分別是：（初始關鍵數據：X=49） 注意關鍵X永遠不變，永遠是和X進行比較，無論在什麼位子，最後的目的就是把X放在中間，小的放前面大的放後面。
A[0] 、 A[1]、 A[2]、 A[3]、 A[4]、 A[5]、 A[6]： 49 38 65 97 76 13 27
進行第一次交換後： 27 38 65 97 76 13 49 ( 按照演算法的第三步從後面開始找)
進行第二次交換後： 27 38 49 97 76 13 65 ( 按照演算法的第四步從前面開始找>X的值，65>49,兩者交換，此時：I=3 )
進行第三次交換後： 27 38 13 97 76 49 65 ( 按照演算法的第五步將又一次執行演算法的第三步從後開始找
進行第四次交換後： 27 38 13 49 76 97 65 ( 按照演算法的第四步從前面開始找大於X的值，97>49,兩者交換，此時：I=4,J=6 )
此時再執行第三步的時候就發現I=J，從而結束一趟快速排序，那麼經過一趟快速排序之後的結果是：27 38 13 49 76 97 65，即所以大於49的數全部在49的後面，所以小於49的數全部在49的前面。
快速排序就是遞歸調用此過程——在以49為中點分割這個數據序列，分別對前面一部分和後面一部分進行類似的快速排序，從而完成全部數據序列的快速排序，最後把此數據序列變成一個有序的序列，根據這種思想對於上述數組A的快速排序的全過程如圖6所示：
初始狀態 {49 38 65 97 76 13 27}
進行一次快速排序之後劃分為 {27 38 13} 49 {76 97 65}
分別對前後兩部分進行快速排序 {27 38 13} 經第三步和第四步交換後變成 {13 27 38} 完成排序。
{76 97 65} 經第三步和第四步交換後變成 {65 76 97} 完成排序。
//c語言快速排序法:
#include<stdio.h>
void run(int *pData,int left,int right)
{
int i,j;
int middle,iTemp;
i=left;
j=right;
middle=pData[(left+right)/2];//求中間值
do
{
while((pData[i]<middle)&&(i<right))//從左掃描大於中值的數
i++;
while((pData[j]>middle)&&(j>left))//從右掃描大於中值的數
j--;
if(i<=j)//找到了一對值
{//交換
iTemp=pData[i];
pData[i]=pData[j];
pData[j]=iTemp;
i++;
j--;
}
}
while(i<=j);//如果兩邊掃描的下標交錯，就停止（完成一次）
if(left<j)//當左邊部分有值(left＜j)，遞歸左半邊
run(pData,left,j);
if(right>i)//當右邊部分有值(right＞i)，遞歸右半邊
run(pData,i,right);
}

void QuickSort(int *pData,int Count)
{
run(pData,0,Count-1);
}
void main()
{
int data[10];
for(int i=9,j=0;i>=0;i--,j++)
data[j]=i;
QuickSort(data,10);
for(int k=0;k<10;k++)
cout<<data[k]<<" ";
cout<<"\n";
}

直接來分析演算法：首先我們考慮最理想的情況
1.數組的大小是2的冪，這樣分下去始終可以被2整除。假設為2的k次方，即k＝log2(n)。
2.每次我們選擇的值剛好是中間值，這樣，數組才可以被等分。
第一層遞歸，循環n次，第二層循環2＊(n/2)......
所以共有n+2(n/2)+4(n/4)+...+n＊(n/n) ＝ n+n+n+...+n＝k＊n＝log2(n)＊n
所以演算法復雜度為O(log2(n)＊n)
==========================================================================

希爾排序(Shell Sort)是插入排序的一種。是針對直接插入排序演算法的改進。該方法又稱縮小增量排序，因DL．Shell於1959年提出而得名。
希爾排序基本思想：
先取一個小於n的整數d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為dl的倍數的記錄放在同一個組中。先在各組內進行直接插入排序；然後，取第二個增量d2<d1重復上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。 該方法實質上是一種分組插入方法。
給定實例的shell排序的排序過程
假設待排序文件有10個記錄，其關鍵字分別是：
49，38，65，97，76，13，27，49，55，04。
增量序列的取值依次為： 5，3，1
希爾排序(縮小增量法) 屬於插入類排序,是將整個無序列分割成若干小的子序列分別進行插入排序 排序過程：先取一個正整數d1<n，把所有序號相隔d1的數組元素放一組，組內進行直接插入排序；然後取d2<d1，重復上述分組和排序操作；直至di=1，即所有記錄放進一個組中排序為止
初始：d＝5
49 38 65 97 76 13 27 49* 55 04
49 13
|-------------------|
38 27
|-------------------|
65 49*
|-------------------|
97 55
|-------------------|
76 04
|-------------------|
一趟結果
13 27 49* 55 04 49 38 65 97 76
d=3
13 27 49* 55 04 49 38 65 97 76
13 55 38 76
|------------|------------|------------|
27 04 65
|------------|------------|
49* 49 97
|------------|------------|
二趟結果
13 04 49* 38 27 49 55 65 97 76
d=1
13 04 49* 38 27 49 55 65 97 76
|----|----|----|----|----|----|----|----|----|
三趟結果
04 13 27 38 49* 49 55 65 76 97
--------------------------------------------------------------------------------------------
演算法思想簡單描述： 在直接插入排序演算法中，每次插入一個數，使有序序列只增加1個節點， 並且對插入下一個數沒有提供任何幫助。如果比較相隔較遠距離（稱為 增量）的數，使得數移動時能跨過多個元素，則進行一次比較就可能消除 多個元素交換。D.L.shell於1959年在以他名字命名的排序演算法中實現 了這一思想。演算法先將要排序的一組數按某個增量d分成若干組，每組中 記錄的下標相差d.對每組中全部元素進行排序，然後再用一個較小的增量 對它進行，在每組中再進行排序。當增量減到1時，整個要排序的數被分成 一組，排序完成。 下面的函數是一個希爾排序演算法的一個實現，初次取序列的一半為增量， 以後每次減半，直到增量為1。 希爾排序是不穩定的。

希爾排序的C#實現
using System;
public class ShellSorter
{
public void Sort(int[] list)
{
int inc;
for (inc = 1; inc <= list.Length / 9; inc = 3 * inc + 1) ;
for (; inc > 0; inc /= 3)
{
for (int i = inc + 1; i <= list.Length; i += inc)
{
int t = list[i - 1];
int j = i;
while ((j > inc) && (list[j - inc - 1] > t))
{
list[j - 1] = list[j - inc - 1];
j -= inc;
}
list[j - 1] = t;
}
}
}
}
public class MainClass
{
public static void Main()
{
int[] iArrary = new int[] { 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 };
ShellSorter sh = new ShellSorter();
sh.Sort(iArrary);
for (int m = 0; m <= 13; m++)
Console.WriteLine("{0}", iArrary[m]);
Console.ReadKey();
}
}

B. 快速排序演算法有什麼作用

首先它是一種排序演算法，排序演算法是為了讓無序的數據組合變成有序的數據組合。

有序的數據組合最大的優勢是在於當你進行數據定位和採用時，
會非常方便，因為這個數據是有序的
從而在代碼設計的時候會讓你避免很多不必要的麻煩，
因為無序數據你在進行推斷數據前後關系的時候會顯示很繁瑣

快速排序是排序中的一種，它在最差情況下和別的排序相差不大
而在最優，一般情況下，會比一般的排序方法更節省時間

這里的一般排序是指：起泡，希爾，插入等常規排序方法

其實我個人更喜歡插入，不過這對於鏈表操作更方便，因為容易操作……

C. 求問關於快速排序演算法

當然變了啊 你說的i是快排的區間起始節點吧

D. 寫出快速排序的演算法

快速排序演算法通過多次比較和交換來實現排序，其排序演算法如下：
(1)首先設定一個分界值，通過該分界值將數組分成左右兩部分。
(2)將大於或等於分界值的數據集中到數組右邊，小於分界值的數據集中到數組的左邊。此時，左邊部分中各元素都小於或等於分界值，而右邊部分中各元素都大於或等於分界值。
(3)然後，左邊和右邊的數據可以獨立排序。對於左側的數組數據，又可以取一個分界值，將該部分數據分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側的數組數據也可以做類似處理。
(4)重復上述過程，可以看出，這是一個遞歸定義。通過遞歸將左側部分排好序後，再遞歸排好右側部分的順序。當左、右兩個部分各數據排序完成後，整個數組的排序也就完成了。

E. C++快速排序演算法

int qpass(RecordYype r[],int left,int right)/*對記錄數組r中的r[left]至r[right]部分進行一趟排序，並得到樞軸的位置，使得排序後的結果滿足期之後（前）的記錄的關鍵字均不小於（大於）樞軸記錄*/
{
x=r[left];
low=left; high=right;
while(low<high)
{
while(low<high&&r[high].key>=x.key) /*high從右向左找小於x.key的記錄*/
high--;
if(low<high) {r[low]=r[high]; low++;} /*找到小於x.key的記錄，則進行交換*/
while(low<high&&r[left].key<=x.key ) /*low從左到右找大於x.key的記錄*/
if(low<high) {r[high]=r[low]; high--;} /*找到大於x.key的記錄，則進行交換*/
}
r[low]=x; /*將樞軸記錄保存到low=high的位置*/
return low; /*返回樞軸記錄的位置*/
}

F. 快速排序法，

66 13 51 76 81 26 57 69 23
23 13 51 76 81 26 57 69 66
23 13 51 66 81 26 57 69 76
23 13 51 57 81 26 66 69 76
23 13 51 57 66 26 81 69 76
23 13 51 57 26 66 81 69 76

第一次排序過程如上
void sort(int *a,int l,int r)
{
int k=a[l],i=l,j=r;
while (i<j)
{
while (i<j)
{
if (a[j]<k) {swap(a[i],a[j]);print(a,n); break;}
j--;
}
while (i<j)
{
if (a[i]>k) {swap(a[i],a[j]);print(a,n); break;}
i++;
}
}

if (i-l>=1) sort(a,l,i);
if (r-i-1>=1) sort(a,i+1,r);

｝

G. 關於快速排序演算法

當待排序區間中的關鍵碼都相同，也就是快速排序的最壞情況，其運行時間是
O(n^2)，然而但在關鍵碼不全相同時，如果總是選擇中項作為主元，它的時間復雜性是O(nlogn)。
盡管在最壞情況下，快排表現出的運行時間為O（n^2），但它的平均時間復雜度仍是O(nlogn)。

H. 快速排序演算法原理與實現

快速排序的原理：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小。

然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

假設要排序的數組是A[1]……A[N]，首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然後將所有比它的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一躺快速排序。一躺快速排序的演算法是：

1、設置兩個變數I、J，排序開始的時候I：=1，J：=N；

2、以第一個數組元素作為關鍵數據，賦值給X，即X：=A[1]；

3、從J開始向前搜索，即由後開始向前搜索（J：=J-1），找到第一個小於X的值，兩者交換；

4、從I開始向後搜索，即由前開始向後搜索（I：=I+1），找到第一個大於X的值，兩者交換；

5、重復第3、4步，直到I=J。

(8)快速排序方法擴展閱讀：

設要排序的數組是A[0]……A[N-1]，首先任意選取一個數據（通常選用數組的第一個數）作為關鍵數據，然後將所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序。

值得注意的是，快速排序不是一種穩定的排序演算法，也就是說，多個相同的值的相對位置也許會在演算法結束時產生變動。

一趟快速排序的演算法是：

1、設置兩個變數i、j，排序開始的時候：i=0，j=N-1；

2、以第一個數組元素作為關鍵數據，賦值給key，即key=A[0]；

3、從j開始向前搜索，即由後開始向前搜索(j--)，找到第一個小於key的值A[j]，將A[j]的值賦給A[i]；

4、從i開始向後搜索，即由前開始向後搜索(i++)，找到第一個大於key的A[i]，將A[i]的值賦給A[j]；

5、重復第3、4步，直到i=j； (3,4步中，沒找到符合條件的值，即3中A[j]不小於key,4中A[i]不大於key的時候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進行交換的時候i， j指針位置不變。