243
[算法係列之五]快速排序
【分析】
【偽代碼】
【思路圖】
【運行過程】
【代碼】
/*********************************
* 日期：2014-04-01
* 作者：SJF0115
* 題目：快速排序
**********************************/
#include <iostream>
#include <stdio.h>
using namespace std;
//對子數組array[p...r]就地重排
int Partition(int array[],int p,int r){
int j,temp;
//定義哨兵
int x = array[r];
//i為小於哨兵元素的最後一個元素下標
int i = p - 1;
//j為待排序元素的第一個元素
for(j = p;j < r;j++){
//跟哨兵比較
if(array[j] < x){
i++;
//交換array[i] array[j]
temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
//交換array[i+1](大於哨兵元素的第一個元素) array[r]
temp = array[i+1];
array[i+1] = array[r];
array[r] = temp;
//返回分割下標
return i + 1;
}
//快排
void QuickSort(int array[],int p,int r){
if(p >= r || array == NULL){
return;
}
int index = Partition(array,p,r);
QuickSort(array,p,index-1);
QuickSort(array,index+1,r);
}
int main()
{
int array[] = {2,8,7,1,3,5,6,4};
QuickSort(array,0,7);
for(int i = 0;i <= 7;i++){
printf("%d\n",array[i]);
}
}
最後更新：2017-04-03 12:56:29