目錄

快速排序

直接插入排序

改良版冒泡排序

---

快速排序

理解：

①從待排序元素中選定一個基準元素；

②以基準元素將數(shù)據(jù)分為兩部分：（可以將：大于基準元素放左，小于基準元素放右）

③對左半部分（從左端到基準數(shù)據(jù)）進行①②操作；直到數(shù)據(jù)有序

????即將左端到基準數(shù)據(jù)作為范圍，傳入；這個范圍又會產(chǎn)生新的范圍：左端到基準數(shù)據(jù)2；

????……

????直到數(shù)據(jù)有序

④對左半部分（從基準數(shù)據(jù)到右端）進行①②操作；

【粗劣分析：便于理解】

右半部分：

【深層分析：便于代碼】

遍歷直倒有序：

數(shù)據(jù)有序后返回上一層

代碼思路

/*

思路：

選定一個基準(默認左端): ? 用變量temp記錄基準值;

loop:

此時左端所在下標low代表的值可以被覆蓋(值已經(jīng)被復制了)

從右端向左端的方向,開始與temp比較,直到遇到比temp小的數(shù),(否則就high--左移),將這個小于temp的數(shù)(下標可假定為high')放到左邊，左邊下標low所在的數(shù)據(jù)上

此時右端所在下標high代表的值可以被覆蓋(值已經(jīng)復制到下標low代表的值內(nèi)了)

從左端向左端的方向,開始與temp比較,直到遇到比temp大的數(shù),(否則就low++后移),將這個大于temp的數(shù)(下標可假定為low')放到右邊，左邊下標high所在的數(shù)據(jù)上

此時左端low'下標的數(shù)據(jù)可以被覆蓋，回到loop;

循環(huán)結束條件:low'后移high'前移 直到相遇，說明以基準值temp將這批數(shù)據(jù)分成兩份完畢。

注意：此時大小兩份雖然分類完成，但是 作為基準值的數(shù)據(jù) 還未找到位置；【基準值應該放在下標為low的位置】

看下面圖理解

注意，此時應low==high并且理應必須low==high，

注意，此時下標所在位置的數(shù)據(jù)應該被覆蓋，

故基準值應該放在下標為low的位置(或者下標為high，反正兩值相等)

*********************************************************

《基準值臨界情形圖》

基準值5

x x x x 6 3 x x x

? ? ? ? l h ? ? 此時基準值正在與l所代表元素比較l向右移中（說明h位置是無用數(shù)據(jù)）

x x x x 6 6 x x x

? ? ? ? l h ? ? l數(shù)據(jù)復制給h,輪到下標h向左移動

x x x x 6 6 x x x

? ? ? ? ↑ ? ? ? 兩下標重合相等，此時應該放入基準值temp(h現(xiàn)在是無用數(shù)據(jù))(low左邊比基準值小，high右邊比基準值大)

基準值7

x x x x 6 5 x x

? ? ? ? l h ? ? 此時基準值正在與l所代表元素比較h向左移動中（說明l位置是無用數(shù)據(jù)）

x x x x 5 5 x x

? ? ? ? l h ? ? h數(shù)據(jù)復制給l,輪到下標l向左移動(h現(xiàn)在是無用數(shù)據(jù))

x x x x 5 5 x x

? ? ? ? ? ↑ ? ? 兩下標重合相等，此時應該放入基準值temp(h現(xiàn)在是無用數(shù)據(jù))(low左邊比基準值小，high右邊比基準值大)

*********************************************************

*/

全部代碼：

#include <stdio.h>//顯示函數(shù)
void showData(int buf[],int len)
{//顯示for(int i=0;i<len;i++)printf("%d ",buf[i]);printf("\n");
}//快速排序函數(shù)/*************************************************************************
函數(shù)功能:   對傳入的數(shù)據(jù)進行一次快速排序（分成大于基準值和小于基準值的兩部分）；
輸入?yún)?shù):   待排序的數(shù)組，需要排序的下標范圍（左端下標、右端下標）;
返回值：    基準所在的下標
*************************************************************************/
/*
思路：
選定一個基準(默認左端):   用變量temp記錄基準值;loop:
此時左端所在下標low代表的值可以被覆蓋(值已經(jīng)被復制了)
從右端向左端的方向,開始與temp比較,直到遇到比temp小的數(shù),(否則就high--左移),將這個小于temp的數(shù)(下標可假定為high')放到左邊，左邊下標low所在的數(shù)據(jù)上此時右端所在下標high代表的值可以被覆蓋(值已經(jīng)復制到下標low代表的值內(nèi)了)
從左端向左端的方向,開始與temp比較,直到遇到比temp大的數(shù),(否則就low++后移),將這個大于temp的數(shù)(下標可假定為low')放到右邊，左邊下標high所在的數(shù)據(jù)上此時左端low'下標的數(shù)據(jù)可以被覆蓋，回到loop;循環(huán)結束條件:low'后移high'前移 直到相遇，說明以基準值temp將這批數(shù)據(jù)分成兩份完畢。注意：此時大小兩份雖然分類完成，但是 作為基準值的數(shù)據(jù) 還未找到位置；【基準值應該放在下標為low的位置】看下面圖理解
注意，此時應low==high并且理應必須low==high，
注意，此時下標所在位置的數(shù)據(jù)應該被覆蓋，
故基準值應該放在下標為low的位置(或者下標為high，反正兩值相等)
*********************************************************
《基準值臨界情形圖》
基準值5
x x x x 6 3 x x xl h     此時基準值正在與l所代表元素比較l向右移中（說明h位置是無用數(shù)據(jù)）
x x x x 6 6 x x xl h     l數(shù)據(jù)復制給h,輪到下標h向左移動
x x x x 6 6 x x x↑       兩下標重合相等，此時應該放入基準值temp(h現(xiàn)在是無用數(shù)據(jù))(low左邊比基準值小，high右邊比基準值大)
基準值7
x x x x 6 5 x x l h     此時基準值正在與l所代表元素比較h向左移動中（說明l位置是無用數(shù)據(jù)）
x x x x 5 5 x xl h     h數(shù)據(jù)復制給l,輪到下標l向左移動(h現(xiàn)在是無用數(shù)據(jù))
x x x x 5 5 x x↑     兩下標重合相等，此時應該放入基準值temp(h現(xiàn)在是無用數(shù)據(jù))(low左邊比基準值小，high右邊比基準值大)
*********************************************************
*/int part(int arr[],int low,int high)
{//檢查輸入范圍是否合法if(low>high){return -1;}//選定一個基準值(以左端作為基準值)int temp=arr[low];//注意:下標low所在數(shù)據(jù)被temp保存//結束循環(huán)的條件while(low<high){//比較右端,比基準大的仍然放在右邊，不用管，繼續(xù)向前判斷下一個:故high--;while(temp<arr[high]&&low<high){high--;//下標向前移動，判斷下一個}//條件不滿足時出循環(huán)，將這個小數(shù)據(jù)放到左邊，下標為low的地方(low數(shù)據(jù)已經(jīng)被保存)arr[low]=arr[high];//開始比較左端:比基準小得仍然放左邊，繼續(xù)向后判斷下一個while(temp>arr[low]&&low<high){low++;}//條件不滿足，跳出循環(huán)，將這個小數(shù)據(jù)放到左邊arr[high]=arr[low];//此時high所在數(shù)據(jù)，之前已經(jīng)被放到循環(huán)前的low里了/*注意:這里內(nèi)層循環(huán)增設了條件為low<high,圖形解釋:   見最下方《基準值臨界情形圖》PRO文字解釋:當low與high相差為1時，假定low與low將值給high，開始判斷high,此時high的值必定會滿足，所以high會左移high移動到low的位置，仍然會滿足值的條件條件high繼續(xù)移動到low的左邊，此時high值不滿足條件；出循環(huán)并且交換數(shù)據(jù)；回到大循環(huán)，判斷l(xiāng)ow<high*/}//運行到此，說明low==high;arr[high]=temp;return high;//基準所在下標low或者high都可以
}void quick_sort(int arr[],int low,int high)
{if(low>=high){return;}int mid=part(arr,low,high);quick_sort(arr,low,mid-1);quick_sort(arr,mid+1,high);
}int main()
{int arr[]={82,15,49,85,28,43,39,17,47,48};int len=sizeof(arr)/sizeof(arr[0]);printf("len=%d\n",len);//快速排序quick_sort(arr,0,9);//數(shù)據(jù)顯示showData(arr,len);
}/*
*********************************************************
《基準值臨界情形圖》PRO     臨界情形分析
基準值5
x x x x 6 3 x x xl h     此時基準值正在與l所代表元素比較l向右移中（說明h位置是無用數(shù)據(jù)）
x x x x 6 6 x x xl h     l數(shù)據(jù)復制給h,輪到下標h向左移動
x x x x 6 6 x x x↑       兩下標重合相等，此時應該放入基準值temp(h現(xiàn)在是無用數(shù)據(jù))
x x x x 6 6 x x xh l       內(nèi)層循環(huán)不加low<high;則h會一直移動！直到小于基準值，才回到外層循環(huán)判斷l(xiāng)ow<high
基準值7
x x x x 6 5 x x l h     此時基準值正在與l所代表元素比較h向左移動中（說明l位置是無用數(shù)據(jù)）
x x x x 5 5 x xl h     h數(shù)據(jù)復制給l,輪到下標l向左移動(h現(xiàn)在是無用數(shù)據(jù))
x x x x 5 5 x x↑     兩下標重合相等，此時應該放入基準值temp(h現(xiàn)在是無用數(shù)據(jù))
x x x x 5 5 x xh l   內(nèi)層循環(huán)不加low<high;則l會一直移動！直到大于基準值，才回到外層循環(huán)判斷l(xiāng)ow<high
*********************************************************
*/

直接插入排序

//直接插入排序
void insert_sort(int arr[],int len)
{for(int i=1;i<len;i++)//{int temp=arr[i];//選定第i個，進行插入int j;for(j=i-1;j>=0&&arr[j]>temp;j--)//將在"我"之前的數(shù)據(jù)，依次向后搬運，直到遇到第一個比自己小的元素{arr[j+1]=arr[j];}arr[j+1]=temp;//插入位置！注意執(zhí)行了"j--"才出的循環(huán)}
}

改良版冒泡排序

//改良版冒泡排序
void bubble_sort(int buf[],int len)
{int temp;int flag=1;for(int i=0;i<len&&flag;i++)//輪數(shù){flag=0;//使用標志位前，標志位初始值for(int j=0;j<len-1-i;j++)//每輪比較次數(shù){if(buf[j]>buf[j+1]){flag=1;//發(fā)生交換，標志位置1temp=buf[j+1];buf[j+1]=buf[j];buf[j]=temp;}}//一輪下來沒有發(fā)生交換，排序已完成，跳出循環(huán)}
}