導航:首頁 > 源碼編譯 > 快速排序演算法c語言同向運行

快速排序演算法c語言同向運行

發布時間:2023-01-25 07:51:05

『壹』 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語言

quick明顯有問題,1.存在死循環2.使用遞歸是想實現什麼?

如果想實現快速排序的話可以參考一下程序段,盡量精簡交換操作增加排序速度:

voidquick(int*arr,intlen)
{
inti,j,k,z;
for(i=0;i<len-1;i++)
{
for(j=0,k=0;j<len-i-1;j++)
{
if(arr[k]<arr[j+1])
k=j+1;
}
if(k!=len-i-1)
{
z=arr[len-i-1];
arr[len-i-1]=arr[k];
arr[k]=z;
}
}
}

『叄』 C語言中快速排序法的原理及應用

「快速排序法」使用的是遞歸原理,下面我結合一個例子來說明「快速排序法」的原理。首先給出一個數組{53,12,98,63,18,72,80,46, 32,21},先找到第一個數--53,把它作為中間值,也就是說,要把53放在一個位置,使得它左邊的值比它小,右邊的值比它大。{21,12,32, 46,18,53,80,72,63,98},這樣一個數組的排序就變成了兩個小數組的排序--53左邊的數組和53右邊的數組,而這兩個數組繼續用同樣的方式繼續下去,一直到順序完全正確。

一般來說,冒泡法是程序員最先接觸的排序方法,它的優點是原理簡單,編程實現容易,但它的缺點就是--程序的大忌--速度太慢。

附上快速排序代碼:

#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語言 快速排序

首先,你要理解快速排序的演算法,它是一種遞歸的演算法。每次選擇一個基準,讓該基準左邊的數全小與他,右邊的全大於它,這樣就是一次循環,將數據分成兩段,每次再找基準分成兩段。
if (s1<j) qsort(s1,i);
if (s2>i) qsort(i,s2);
就是在分成的左右兩段中再排序。

『伍』 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語言編程實現快速排序演算法

給個快速排序你參考參考

/**********************快速排序****************************
基本思想:在待排序的n個記錄中任取一個記錄(通常取第一個記錄),
以該記錄為基準,將當前的無序區劃分為左右兩個較小的無
序子區,使左邊的記錄均小於基準值,右邊的記錄均大於或
等於基準值,基準值位於兩個無序區的中間位置(即該記錄
最終的排序位置)。之後,分別對兩個無序區進行上述的劃
分過程,直到無序區所有記錄都排序完畢。
*************************************************************/

/*************************************************************
函數名稱:staticvoidswap(int*a,int*b)
參數:int*a---整型指針
int*b---整型指針
功能:交換兩個整數的位置
返回值:無
說明:static關鍵字指明了該函數只能在本文件中使用
**************************************************************/
staticvoidswap(int*a,int*b)
{
inttemp=*a;
*a=*b;
*b=temp;
}

intquickSortNum=0;//快速排序演算法所需的趟數
/*************************************************************
函數名稱:staticintpartition(inta[],intlow,inthigh)
參數:inta[]---待排序的數據
intlow---無序區的下限值
inthigh---無序區的上限值
功能:完成一趟快速排序
返回值:基準值的最終排序位置
說明:static關鍵字指明了該函數只能在本文件中使用
**************************************************************/
staticintpartition(inta[],intlow,inthigh)
{
intprivotKey=a[low];//基準元素
while(low<high)
{//從表的兩端交替地向中間掃描
while(low<high&&a[high]>=privotKey)//找到第一個小於privotKey的值
high--;//從high所指位置向前搜索,至多到low+1位置
swap(&a[low],&a[high]);//將比基準元素小的交換到低端

while(low<high&&a[low]<=privotKey)//找到第一個大於privotKey的值
low++;//從low所指位置向後搜索,至多到high-1位置
swap(&a[low],&a[high]);//將比基準元素大的交換到高端
}
quickSortNum++;//快速排序趟數加1
returnlow;//返回基準值所在的位置
}

/*************************************************************
函數名稱:voidQuickSort(inta[],intlow,inthigh)
參數:inta[]---待排序的數據
intlow---無序區的下限值
inthigh---無序區的上限值
功能:完成快速排序演算法,並將排序完成的數據存放在數組a中
返回值:無
說明:使用遞歸方式完成
**************************************************************/
voidQuickSort(inta[],intlow,inthigh)
{
if(low<high)
{
intprivotLoc=partition(a,low,high);//將表一分為二
QuickSort(a,low,privotLoc-1);//遞歸對低子表遞歸排序
QuickSort(a,privotLoc+1,high);//遞歸對高子表遞歸排序
}
}
閱讀全文

與快速排序演算法c語言同向運行相關的資料

熱點內容
java實體註解 瀏覽:830
網頁小游戲源碼下載 瀏覽:75
房產未解壓買房者如何規避風險 瀏覽:482
一物一碼app是什麼軟體 瀏覽:660
php獲取匹配 瀏覽:443
為啥macbook文件夾打開沒有東西 瀏覽:74
蘋果應用商店下app怎麼收費 瀏覽:688
單片機定時器取余和取整 瀏覽:308
臨沭車輛解壓在哪裡 瀏覽:685
安卓智能手錶如何聽歌 瀏覽:542
win10文件夾取消分組折疊組 瀏覽:664
趨勢指標源碼分析 瀏覽:418
股票價格計算公式源碼 瀏覽:767
程序員解釋方向問題 瀏覽:831
安卓手機關閉屏幕怎麼錄音 瀏覽:232
為什麼老顯示伺服器連接失敗 瀏覽:419
滴答滴app上如何拼車 瀏覽:872
網路加密了怎麼用手機連接 瀏覽:53
香腸樹app等級怎麼看 瀏覽:364
解壓模擬器3d抖音小游戲 瀏覽:319