[C/C++ 演算法]-資料結構與演算法(文魁)：快速排序

 

線上執行結果：http://www.tutorialspoint.com/compile_c_online.php

code2html：http://tohtml.com/

  

/* =============== Program Description =============== */
/* 程式名稱 : 6_8.cpp				       */
/* 程式目的 : 快速排序				       */
/* 輸    入 : 排序前的整數陣列資料		       */
/* 輸    出 : 排序後的整數陣列資料		       */
/* =================================================== */
#define n 20
// 宣告標頭檔
#include "stdio.h"
// 宣告函式原型
// 利用傳址的方式把Array A傳進quick_sort函式中
void quick_sort(int *A,int left,int right);
// 利用傳參考的方式把Value1,Value2兩個變數,傳入swap函式中
void swap(int *Value1, int *Value2);
void main(void)
{
int i;
int A[n]={1,21,0,47,60,
15,84,65,77,88,
100,93,8,17,36,
5,24,63,72,20};
// 排序前的資料
printf(" Data before sorting \n");
for(i=0;i<n;i++)
printf("%d",A[i]);
printf("\n");
quick_sort(A,0,n-1);
// 排序後的資料
printf(" Data after sorting \n");
for(i=0;i<n;i++)
printf("%d",A[i]);
printf("\n");
getchar();
}
void quick_sort(int *A,int left,int right)
{
int low,upper, point;
if(left < right) {
point = A[left];
low = left;
upper = right + 1;
while(1) {
while(A[++low] < point) ;    // 向右找 
while(A[--upper] > point) ;  // 向左找 
if(low >= upper)
break;
swap(&A[low], &A[upper]);
}
A[left] = A[upper];
A[upper] = point;
quick_sort(A, left, upper-1);   // 對左邊進行遞迴 
quick_sort(A, upper+1, right);  // 對右邊進行遞迴 
}
}
void swap(int *Value1, int *Value2)
{
int temp;
temp = *Value2;
*Value2 = *Value1;
*Value1 = temp;
}