快速排序(QuickSort)是冒泡排序的優化算法。
基本思想：通過一趟排序將待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字比另一部分記錄的關鍵字小，則可以分別對這兩部分記錄繼續進行快速排序，以達到整個序列有序的目的。
樞軸pivot)：選取待排序列當中的一個關鍵字，然後想盡辦法把它放到一個位置，使得它左邊的值都比它小，右邊的值都比它大，我們將這樣的關鍵字成為樞軸pivot)。
一般取待排序最左端的那個關鍵字為樞軸。
#include <stdio.h>
#include <stdlib.h>
void swap(int arr[] ,int i, int j)
{
int temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//將待排序的數組分為兩個部分，樞軸左面的值都比樞軸值小，右面的值都比樞軸值大，函數返回值pivot為樞軸所在的位置
int Partition(int arr[], int low, int high)
{
int pivotkey; //樞軸值
pivotkey = arr[low]; //取待排序的第一個值為樞軸值
while(low < high)
{
while(low < high && arr[high] >= pivotkey)
high--;
swap(arr, low, high); // 將比樞軸記錄小的記錄交換到低端
while(low < high && arr[low] <= pivotkey)
low++;
swap(arr, low, high); //將比樞軸記錄大的記錄交換到高端
}
return low; //返回樞軸所在的位置
}
void QuickSort(int arr[], int low, int high)
{
int pivot; //樞軸值
if(low < high)
{
pivot = Partition(arr, low, high); //將待排序的數組分為兩個部分，樞軸左面的值都比樞軸值小，右面的值都比樞軸值大，pivot為樞軸所在的位置
QuickSort(arr, low, pivot-1); //將樞軸值左面的 序列 重新快速排序
QuickSort(arr, pivot+1, high); //將樞軸值右面的 序列 重新快速排序
}
}
void print(int arr[], int n)
{
int i;
for(i=0; i<n; i++)
{
printf("%d ",arr[i]);
}
printf("\n");
}
int main()
{
int arr[]={9, 1, 5, 8, 3, 7, 4, 6, 2};
int n = sizeof(arr)/sizeof(arr[0]);
printf("排序前：\n");
print(arr, n);
QuickSort(arr,0,n-1);
printf("排序後：\n");
print(arr, n);
system("pause");
return 0;
}快速排序復雜度分析
最優情況：每次分割成兩部分都很均勻，即兩部分的數據相差不多。僅需遞歸logn次，算法時間復雜度為O(nlogn)
最壞情況：待排序為正序或反序，每次分割，都是一邊為空，需要執行n-1次遞歸調用，且第i次劃分需要經過n-i次的比較，因此比較次數為n-1+n-2+...+1=n(n-1)/2。其時間復雜度為O(n2)。
平均情況：
復雜度為O(nlogn)；
快速排序是不穩定的排序。
本文出自 “李海川” 博客，請務必保留此出處http://lihaichuan.blog.51cto.com/498079/1282083
