快排演算法c
1、「快速排序法」使用的是遞歸原理，下面一個例子來說明「快速排序法」的原理。首先給出一個數組{53，12，98，63，18，72，80，46， 32，21}，先找到第一個數--53，把它作為中間值，也就是說，要把53放在一個位置，使得它左邊的值比它小，右邊的值比它大。{21，12，32， 46，18，53，80，72，63，98}，這樣一個數組的排序就變成了兩個小數組的排序--53左邊的數組和53右邊的數組，而這兩個數組繼續用同樣的方式繼續下去，一直到順序完全正確。一般來說，冒泡法是程序員最先接觸的排序方法，它的優點是原理簡單，編程實現容易，但它的缺點就是速度太慢。
2、快速排序代碼：
#include<stdio.h>
voidquicksort(inta[],intleft,intright)
{
inti,j,temp;
i=left;
j=right;
temp=a[left];
if(left>right)
return;
while(i!=j)
{
while(a[j]>=temp&&j>i)
j--;
if(j>i)
a[i++]=a[j];
while(a[i]<=temp&&j>i)
i++;
if(j>i)
a[j--]=a[i];
}
a[i]=temp;
quicksort(a,left,i-1);
quicksort(a,i+1,right);
}
voidmain()
{
inta[]={53,12,98,63,18,72,80,46,32,21};
inti;
quicksort(a,0,9);
/*排好序的結果*/
for(i=0;i<10;i++)
printf("%4d ",a[i]);
}
② C++快排的問題
下面這個答案可能對你有幫助，（不是原創）
1.穩定性比較
插入排序、冒泡排序、二叉樹排序、二路歸並排序及其他線形排序是穩定的
選擇排序、希爾排序、快速排橘罩序、堆排序是不穩定的
2.時間復雜性比較
插入排序、冒泡排序、選擇排序的時間復雜性為O(n2)
其它非線形排序的時間復雜性為O(nlog2n)
線形排序的時間復雜性為O(n);
3.輔助空間的比較
線形排序、二路歸並排序的輔助空間為O(n),其它排序的輔助空間為O(1);
4.其它比較
插入、冒泡排序的速度較慢，但參加排序的序列局部或整體有序時，這種排序能達到較快的速度。反而在這種情況下，快速排序反而慢了。
當n較小時，對穩定性不作要求時宜用選擇排序，對穩定性有要求時宜用插入或冒泡排序。
若待排序的記錄的關鍵字在一個明顯有限范圍內時,且空間允許是用桶排序。
當n較大時，關鍵字元素比較隨機，對穩定性沒要求宜用快速排序。
當n較大時，關鍵字元素可能出現本身是有序的，對穩定性有要求時，空間允許的情況下。宜用歸並排序。
當n較大時，關鍵字元素可能出現本身是有序的，對穩定性沒有要求時宜用堆排序。
相關知識介紹（所有定義只為幫助讀者理解相關概念，並非嚴格定義）：
1、穩定排序和非穩定排序
簡單地說就是所有相等的數經過某種排序方法後，仍能保持它們在排序之前的相對次序，我們就說這種排序方法是穩定的。反之賀伍凳，就是非穩定的。比如：一組數排序前是a1,a2,a3,a4,a5，其中a2=a4，經過某種排序後a1,a2,a4,a3,a5，則我們說這種排序是穩定的，因為a2排序前在a4的前面，排序後它還是在a4的前面。假如變成a1,a4,a2,a3,a5就不是穩定的了。
2、內排序和外排序
在排序過程中，所有需要排序的數都在內存，並在內存中調整它們的存儲順序，稱為內排序；在排序過程中，只有部分數被調入內存，並藉助內存調整數在外存中的存放順序排序方法稱為外排序。
3、演算法的時間復雜度和空間復雜度
所謂演算法的時間復雜度，是指執行演算法所需要的計算工作量。演算法的空間復雜度，一般是指執行這個演算法所需要的內存空間。
================================================
功能：選擇排序
輸入：數組名稱（也就是數組首地址）、數組中元素個數
演算法思想簡單描述：
在要排序的一組數中，選出最小的一個數與第一個位置的數交換；
然後在剩下的數當中再找最小的與第二個位置的數交換，如此循環
到倒數第二個數和最後一個數比較為止。
選擇排序是不穩定的。演算法復雜度O(n^2)--[n的平方]
================================================
功能：直接插入排序
輸入：數組名稱（也就是數組首地址）、數組中元素個數
演算法思想簡單描述：
在要排序的一組數中，假設前面(n-1) [n>=2] 個數已經是排
好順序的，現在要把第n個數插到前面的有序數中，使得這n個數
也是排好順序的。如此反復循環，直到全部排好順序。
直接插入排序是穩定的。演算法時間復雜度O(n^2)--[n的平方]
=====================================================
功能：冒泡排序
輸入：數組名稱（也就是數組首地址）、數組中元素個數
演算法思想簡單描述：
在要排序的一組數中，對禪旅當前還未排好序的范圍內的全部數，自上
而下對相鄰的兩個數依次進行比較和調整，讓較大的數往下沉，較
小的往上冒。即：每當兩相鄰的數比較後發現它們的排序與排序要
求相反時，就將它們互換。
下面是一種改進的冒泡演算法，它記錄了每一遍掃描後最後下沉數的
位置k，這樣可以減少外層循環掃描的次數。
冒泡排序是穩定的。演算法時間復雜度O(n^2)--[n的平方]
================================================
功能：希爾排序
輸入：數組名稱（也就是數組首地址）、數組中元素個數
演算法思想簡單描述：
在直接插入排序演算法中，每次插入一個數，使有序序列只增加1個節點，並對插入下一個數沒有提供任何幫助。如果比較相隔較遠距離（稱為增量）的數，使得數移動時能跨過多個元素，則進行一次比較就可能消除多個元素交換。D.L.shell於1959年在以他名字命名的排序演算法中實現了這一思想。演算法先將要排序的一組數按某個增量d分成若干組，每組中記錄的下標相差d.對每組中全部元素進行排序，然後再用一個較小的增量對它進行，在每組中再進行排序。當增量減到1時，整個要排序的數被分成一組，排序完成。
下面的函數是一個希爾排序演算法的一個實現，初次取序列的一半為增量，以後每次減半，直到增量為1。
希爾排序是不穩定的。
================================================
功能：快速排序
輸入：數組名稱（也就是數組首地址）、數組中起止元素的下標
演算法思想簡單描述：
快速排序是對冒泡排序的一種本質改進。它的基本思想是通過一趟
掃描後，使得排序序列的長度能大幅度地減少。在冒泡排序中，一次
掃描只能確保最大數值的數移到正確位置，而待排序序列的長度可能只
減少1。快速排序通過一趟掃描，就能確保某個數（以它為基準點吧）
的左邊各數都比它小，右邊各數都比它大。然後又用同樣的方法處理
它左右兩邊的數，直到基準點的左右只有一個元素為止。它是由
C.A.R.Hoare於1962年提出的。顯然快速排序可以用遞歸實現，當然也可以用棧化解遞歸實現。下面的函數是用遞歸實現的，有興趣的朋友可以改成非遞歸的。
快速排序是不穩定的。最理想情況演算法時間復雜度O(nlog2n)，最壞O(n^2)--[n的平方]
================================================
功能：堆排序
輸入：數組名稱（也就是數組首地址）、數組中元素個數
演算法思想簡單描述：
堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進。 堆的定義如下：具有n個元素的序列（h1,h2,...,hn),當且僅當滿足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)時稱之為堆。在這里只討論滿足前者條件的堆。由堆的定義可以看出，堆頂元素（即第一個元素）必為最大項。完全二叉樹可以很直觀地表示堆的結構。堆頂為根，其它為左子樹、右子樹。初始時把要排序的數的序列看作是一棵順序存儲的二叉樹，調整它們的存儲序，使之成為一個堆，這時堆的根節點的數最大。然後將根節點與堆的最後一個節點交換。然後對前面(n-1)個數重新調整使之成為堆。依此類推，直到只有兩個節點 的堆，並對它們作交換，最後得到有n個節點的有序序列。從演算法描述來看，堆排序需要兩個過程，一是建立堆，二是堆頂與堆的最後一個元素交換位置。所以堆排序有兩個函數組成。一是建堆的滲透函數，二是反復調用滲透函數實現排序的函數。
堆排序是不穩定的。演算法時間復雜度O(nlog2n)。
③ 請哥哥姐姐為我設計個簡單的快速排序演算法，C語言的，謝謝啦！
void QuickSort(int *a,int left,int right)
{
if ( left < right )
{
int i = left;
int j = right + 1;//why add 1?
int pivot = a[left];//youbiao
do
{
do
{
i++;//the second
} while ( a[i] < pivot );
do
{
j--;
} while ( a[j] > pivot );
if ( i < j )
{
swap(a[i],a[j]);
}
} while ( i < j );
if (left != j)
{
swap(a[left],a[j]);
}
//digui
QuickSort(a,left,j-1);
QuickSort(a,j+1,right);
}
}
//測試排序代碼
void print(int *a,int n)
{
int i;
for ( i = 0 ; i < n ; i++ )
{
printf("%d ",a[i]);
}
printf("\n");
}
int main()
{
int a[20];
myrand(a,20);
QuickSort(a,0,19);
print(a,20);
return 0 ;
}
呵呵 有問題再聯系。。。。
④ 用C語言編寫函數，要實現快速排序演算法或者冒泡法
冒泡法排序函數如下：
void bubble(int a[],int n)
{int i,j,t;
for(i=0;i<n-1;i++)/*共進行n-1輪*/
for(j=0;j<n-1-i;j++)/*每輪在前n-i個數中比較*/
if(a[j]>a[j+1]) /*若相鄰元素逆序*/
{t=a[j]; a[j]=a[j+1];a[j+1]=t;}/*就交換*/
}
void sort(int *a, int left, int right)
{
if(left >= right)/*如果左邊索引大於或者等於右邊的索引就代表已經整理完成一個組了*/
{
return ;
}
int i = left;
int j = right;
int key = a[left];
while(i < j) /*控制在當組內尋找一遍*/
{
while(i < j && key <= a[j])
/*而尋找結束的條件就是，1，找到一個小於或者大於key的數（大於或小於取決於你想升
序還是降序）2，沒有符合條件1的，並且i與j的大小沒有反轉*/
{
j--;/*向前尋找*/
}
a[i] = a[j];
/*找到一個這樣的數後就把它賦給前面的被拿走的i的值（如果第一次循環且key是
a[left]，那麼就是給key）*/
while(i < j && key >= a[i])
/*這是i在當組內向前尋找，同上，不過注意與key的大小關系停止循環和上面相反，
因為排序思想是把數往兩邊扔，所以左右兩邊的數大小與key的關系相反*/
{
i++;
}
a[j] = a[i];
}
a[i] = key;/*當在當組內找完一遍以後就把中間數key回歸*/
sort(a, left, i - 1);/*最後用同樣的方式對分出來的左邊的小組進行同上的做法*/
sort(a, i + 1, right);/*用同樣的方式對分出來的右邊的小組進行同上的做法*/
/*當然最後可能會出現很多分左右，直到每一組的i = j 為止*/
}
⑤ C語言的快速排序的演算法是什麼啊
快速排序（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]，並與key交換； 4）從I開始向後搜索，即由前開始向後搜索（I=I+1），找到第一個大於key的A[I]，與key交換； 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語言誰能告訴我 數據結構和演算法里 快速排序 是怎麼弄的定義兩個指針，和一個關鍵字 具體怎麼弄
快速排序是基於分治思想的排序演算法。
一般的快排是把大於第一個數的放到右邊，小於第一個數前陪的放到左邊，然後再對帶攔分成的兩部分遞歸。
很簡單的一個演算法。
現在這里沒有編譯器，代碼不好敲。如果你理解能力蠢悔胡或動手能力比較差非常需要代碼的話，就追問吧~~
⑦ 快排演算法每趟需要花費多少輔助空間
每趟排舉襪盯序需要一個輔助空間，輔助空間和趟數有關正和，最好情況是log2n ，最差的情況是n。
快速排序由C. A. R. Hoare在1960年提出。
它的基本思想是：通過一趟排序將要排序的數據分割好碰成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
(7)快排演算法c擴展閱讀
一趟快速排序的演算法是：
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指針位置不變。另外，i==j這一過程一定正好是i+或j-完成的時候，此時令循環結束）。
⑧ 菜鳥提問 c語言關於快速排序
其實，最想說明的是那段交換的代碼
R[j]^=R[i];
R[i]^=R[j];
R[j]^=R[i];
一定要排除 i==j 的情況。即自己與自己交換的情況。
如：
a=9;
a^=a;/*a=0*/
a^=a;/*a=0*/
a^=a;/*a=0*/
a就不再是10了。
#include<stdio.h>
#include<stdlib.h>
void quicksort(int R[],int s,int t)
{
int i,j;
int temp;
if(s<t)
{
temp=R[s];/*選第一個數作為參照*/
/*while(i!=j)不要用這種方法判定循環結束，萬一i==j-1，i++，j--後 i〉j了，！=這個條件就救不了你了*/
for(i=s+1,j=t;i<=j;i++,j--)/*不包括參照數，進行老孫譽左右陣營站隊*/
{
while(j>i && R[j]>=temp)/*R[j]>=temp不要 = 也行，加了更好，畢竟相等的無論侍段站左站右，哪邊都無所謂*/
j--;
while(i<j && R[i]<=temp)
i++;
if(i!=j){/*i千萬不能等於j*/
R[j]^=R[i];
R[i]^=R[j];
R[j]^=R[i];
}
}
i--;
if(R[s]<R[i])i--;/*調整i的值，使i指向最後一個小於等於凱碰參照數的位置*/
/*將參照數 與 最後一個小於等於參照數的數進行交換，這樣就真正把左右兩個陣營分開了*/
R[s]=R[i];
R[i]=temp;
quicksort(R,s,i-1);
quicksort(R,i+1,t);
}
}
int main(void)
{
int i;
int a[]={5,3,2,1,9,8,7,4,5};
quicksort(a,0,sizeof(a)/sizeof(int)-1);
for(i=0;i<sizeof(a)/sizeof(int);i++)
printf("%d ",*(a+i));
return 0;
}
⑨ C語言，快速排序演算法
0和N-1表示的是數組下標。快排每一趟排序的目的是使值比設定的key值小的數都排到數組前部分，大的都排到後部分；然後對這兩部分用新的關鍵值key分別重復上一步的操作；遞歸，直到數組有序。
其中關鍵值key=a[low]。
用題目給定的數組模擬第一趟排序如下：
下標0123456789
值91647824661232551
low=0high=9
part_element=a[low]=9
進入for循環
進入第一個while
part_element<51，於是high--,high=8;
part_element<25，high--,high=7;
part_element>3,不滿足，結束while
a[low]=a[0]=a[high]=a[7]=3,low++,low=1;
進入第二個while
part_element<16,不滿足，結束while
a[high]=a[7]=a[low]=a[1]=16,high--,high=6
for第一個循環結束，數組如下
316478246612162551
low=1,high=6
for第二個循環同上，結束時數組如下
344782476612162551
low=2,high=3
for第三個循環，第一個while中high--以後，low==high，直接break跳出for循環，此時
344782476612162551
low=2,high=2
結束for以後
a[high]=a[2]=part_element=9,得到
34982476612162551
split函數returnhigh=2
quicksort函數中middle=2;
下面兩句遞歸，仍然是調用split函數，對數組
0-2,3-9兩部分分別重復上述操作
最後直到數組數據有序
⑩ 用c語言解決快速排序演算法，不用遞歸
可以用循環代替啊。所有的遞歸都是可以用循環加堆棧一類的東西代替的。
但是那會比較惡心，惡心到連本人這么勤奮的好學生都不願意寫……
如果你竟然真的寫了一遍，保證你寫完之伍扒後這輩子不會再想寫第二遍！！！
所以，勸你還是別寫了吧……
其實那玩意就跟數組鄰接表一樣，幾乎沒什麼用
頂多寫出來跟同學顯擺顯擺：瞧，姐會寫不用遞歸的快排$^_^$
我以前就曾經寫過不用指針的數組鄰接表，直接導致了我被大家pia飛~
而且如果你寫那玩意寫多了，就沒人看的懂你的程序了，包括你腔乎昌自己……
（本人的數組鄰接表就是例子！！！）
所以頃哪，有時間還不如去琢磨琢磨其它用處比較大的演算法
另外快排這種東西我不太喜歡，代碼不好寫，時間復雜度未知，如果運氣不好就O(n^2)了……
所以建議你改用堆排，雖然常數項大一點，但是最起碼時間有保證啊！而且代碼好寫又好看，看著四十多行，其實翻來覆去就那幾句話。寫完之後如果縮進合適，遠看起來特別藝術C+_+C