13518219792
#include?stdlib.h
創新互聯建站是一家專注于網站設計制作、成都做網站與策劃設計,香格里拉網站建設哪家好?創新互聯建站做網站,專注于網站建設十年,網設計領域的專業建站公司;建站業務涵蓋:香格里拉等地區。香格里拉做網站價格咨詢:13518219792
#include?stdio.h
#define?MAXN?8
#define?MOD?1024
void?QuickSort(int?*arr,?int?low,?int?high)
{
if?(low?=?high)?return;
//保存排序區間的?起始位置和終點位置
int?left?=?low,?right?=?high;
//默認?左邊第一個元素?為標志
int?key?=?arr[low];
while?(low??high)
{
while?(low??high??arr[high]?=?key)?--high;
arr[low]?=?arr[high];
while?(low??high??arr[low]?=?key)?++low;
arr[high]?=?arr[low];
}
arr[low]?=?key;
//每次排序后都分成兩部分[left,?low)?(low,?right]
//arr[low]的位置是一定是有序的
QuickSort(arr,?left,?low?-?1);
QuickSort(arr,?low?+?1,?right);
return;
}
int?main(void)
{
int?n;
scanf("%d",?n);
int?arr[MAXN]?=?{0};
int?i;
for?(i?=?0;?i??n;?++i)
scanf("%d",?arr[i]);
//輸入是默認為生活中習慣的數組左邊第一個為：編號1
int?s,?m;
scanf("%d?%d",?s,?m);
//轉成計算機數組第一個為：編號0
s--;?m--;
//快排
QuickSort(arr,?s,?m);
//輸出
for?(i?=?s;?i?=?m;?++i)
{
printf("%d?",?arr[i]);
}
return?0;
}
//測試數據
//8
//1?2?3?4?5?6?7?8
//2?6
輸出 6 5 4 3 2
1、冒泡排序（最常用）
冒泡排序是最簡單的排序方法：原理是：從左到右，相鄰元素進行比較。每次比較一輪，就會找到序列中最大的一個或最小的一個。這個數就會從序列的最右邊冒出來。（注意每一輪都是從a[0]開始比較的）
以從小到大排序為例，第一輪比較后，所有數中最大的那個數就會浮到最右邊；第二輪比較后，所有數中第二大的那個數就會浮到倒數第二個位置……就這樣一輪一輪地比較，最后實現從小到大排序。
2、雞尾酒排序
雞尾酒排序又稱雙向冒泡排序、雞尾酒攪拌排序、攪拌排序、漣漪排序、來回排序或快樂小時排序, 是冒泡排序的一種變形。該算法與冒泡排序的不同處在于排序時是以雙向在序列中進行排序。
原理：數組中的數字本是無規律的排放，先找到最小的數字，把他放到第一位，然后找到最大的數字放到最后一位。然后再找到第二小的數字放到第二位，再找到第二大的數字放到倒數第二位。以此類推，直到完成排序。
3、選擇排序
思路是設有10個元素a[1]-a[10]，將a[1]與a[2]-a[10]比較，若a[1]比a[2]-a[10]都小，則不進行交換。若a[2]-a[10]中有一個以上比a[1]小，則將其中最大的一個與a[1]交換，此時a[1]就存放了10個數中最小的一個。同理，第二輪拿a[2]與a[3]-a[10]比較，a[2]存放a[2]-a[10]中最小的數，以此類推。
4、插入排序
插入排序是在一個已經有序的小序列的基礎上，一次插入一個元素*
一般來說，插入排序都采用in-place在數組上實現。
具體算法描述如下：
⒈ 從第一個元素開始，該元素可以認為已經被排序
⒉ 取出下一個元素，在已經排序的元素序列中從后向前掃描
⒊ 如果該元素（已排序）大于新元素，將該元素移到下一位置
⒋ 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置
⒌ 將新元素插入到下一位置中
⒍ 重復步驟2~5
冒泡法排序函數如下：
void bubble(int a[],int n)
{int i,j,t;
for(i=0;in-1;i++)/*共進行n-1輪*/
for(j=0;jn-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 為止*/
}
給個快速排序你參考參考
/**********************?快速排序?****************************
基本思想：在待排序的n個記錄中任取一個記錄（通常取第一個記錄），
??以該記錄為基準，將當前的無序區劃分為左右兩個較小的無
??序子區，使左邊的記錄均小于基準值，右邊的記錄均大于或
??等于基準值，基準值位于兩個無序區的中間位置（即該記錄
??最終的排序位置）。之后，分別對兩個無序區進行上述的劃
??分過程，直到無序區所有記錄都排序完畢。
*************************************************************/
/*************************************************************
函數名稱：static?void?swap(int?*a,?int?*b)
參????數：int?*a---整型指針
??int?*b---整型指針
功????能：交換兩個整數的位置
返?回?值：無
說????明：static關鍵字指明了該函數只能在本文件中使用
**************************************************************/
static?void?swap(int?*a,?int?*b)
{??
int?temp?=?*a;
*a?=?*b;
*b?=?temp;
}
int?quickSortNum?=?0;?//?快速排序算法所需的趟數
/*************************************************************
函數名稱：static?int?partition(int?a[],?int?low,?int?high)
參????數：int?a[]---待排序的數據
??int?low---無序區的下限值
??int?high---無序區的上限值
功????能：完成一趟快速排序
返?回?值：基準值的最終排序位置
說????明：static關鍵字指明了該函數只能在本文件中使用
**************************************************************/
static?int?partition(int?a[],?int?low,?int?high)
{
int?privotKey?=?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
return?low;??//?返回基準值所在的位置
}??
/*************************************************************
函數名稱：void?QuickSort(int?a[],?int?low,?int?high)
參????數：int?a[]---待排序的數據
??int?low---無序區的下限值
??int?high---無序區的上限值
功????能：完成快速排序算法，并將排序完成的數據存放在數組a中
返?回?值：無
說????明：使用遞歸方式完成
**************************************************************/
void?QuickSort(int?a[],?int?low,?int?high)
{??
if(low??high)
{
int?privotLoc?=?partition(a,?low,?high);?//?將表一分為二??
QuickSort(a,?low,?privotLoc-1);??????????//?遞歸對低子表遞歸排序??
QuickSort(a,?privotLoc+1,?high);?????????//?遞歸對高子表遞歸排序??
}
}
你好！
首先?0?，n-1?。應該是?數組的坐標（因為n個數字。所以數組的坐標是0?到n-1）
而a是你傳入的數組。所以他會根據數組的坐標到數組中找到元素。比較并進行排序。
遞歸這段理解如下：
首先要了解快速排序的思想：
1）隨意找一個基準數?。將比基準小的都放到它左邊。比它大的都放到它右邊。所以當返回基準的坐標的時候。其實這個坐標左邊都是小于它的，右邊都是大于等于它的。（這里主要是看代碼的實現。圖中代碼是大于等于在右邊。也可以自己寫小于等于在左邊。這個不影響最后結果）
2）那么第二次對于返回基準坐標的左右兩邊。我們同樣利用返回的基準坐標找到兩個“基準”（如下圖）。就會使得返回的這兩個基準左右兩邊有序
第三次??用返回的兩個基準找到四個基準（如圖）
然后不斷遞歸..不斷的在整體有序的情況下使局部變的有序。
假設?為??532348789
第一次以a【0】?5為基準?。
則：
圖中紅色標識為基準元素?最后會使得數組全局有序。
希望能對你有所幫助。
快速排序（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的值，6549,兩者交換，此時：I=3 ) 進行第三次交換后：27 38 13 97 76 49 65 ( 按照算法的第五步將又一次執行算法的第三步從后開始找 進行第四次交換后：27 38 13 49 76 97 65 ( 按照算法的第四步從前面開始找大于X的值，9749,兩者交換，此時：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} 完成排序。
