前面說了排序算法中的插入排序，下面就來看下排序中的快速排序。
在快速排序中，最簡單的就是大家耳熟能詳的冒泡排序，那麼到底什麼是冒泡排序呢？冒泡排序的思想就是：首先將第一個元素與第二個元素進行比較，若未逆序，則將兩個元素的位置進行交換，然後繼續比較第二個和第三個元素之間的大小，依此類推，知道第n-1個元素和第n個元素比較完成了以後，第一趟冒泡排序就終止了，它將最大的元素安置到了序列的最後，然後在進行第二趟冒泡排序，對前n-1個元素進行冒泡排序，然後將最大值放入n-1的位置上，以此類推，逐趟進行序列的遍歷，而整個排序過程的結束就是在一趟排序中，沒有元素進行交換。
下面就是一個使用冒泡排序的一個小例子：
[cpp]
#include<stdio.h>
#include<stdlib.h>
#define N 100
int L[N];
void Bubblesort(int n)
{
int i,j,t;
for(i=0;i<n;i++)
{
for(j=i;j<=n;j++)
{
if(L[j]>L[j+1])
{ t = L[j+1];
L[j+1] = L[j];
L[j] = t;
continue;
}
}
break;
}
for(i=0;i<=n;i++)
printf("L[%d]=%d\n",i,L[i]);
}
int main()
{
int i,n;
scanf("%d",&n);
for(i=0;i<=n;i++)
scanf("%d",&L[i]);
Bubblesort(n);
return 0;
}
由上面可以明顯的看出，冒泡排序的時間復雜度是O(n2)。其是穩定的排序。
在快速排序中，冒泡排序是最簡單的一種排序，而快速排序是對冒泡排序的一種改進，其算法的基本思想是：通過一趟排序將序列分割成獨立的兩部分，其中一部分的元素比另一部分的元素小，然後將這兩部分序列再進行快速排序排序，以最終達到整個序列有序。快速排序比前面的冒泡排序理解起來稍微有點難度，下面看這個例子，以供大家深入的理解一下：
[cpp]
#include<stdio.h>
#include<stdlib.h>
#define N 100
void Quicksort(int *arr,int StartPos,int EndPos)
{
int i,j,key;
key = arr[StartPos];
i = StartPos;
j = EndPos;
while(i<j)
{
while(arr[j]>=key && i<j)
j--;
arr[i] = arr[j];
while(arr[i]<=key && i<j)
i++;
arr[j] = arr[i];
}
arr[i] = key;
if(i-1>StartPos)
Quicksort(arr,StartPos,i-1);
if(EndPos>i+1)
Quicksort(arr,i+1,EndPos);
}
void Print(int *arr,int EndPos)
{
int i;
for(i=0;i<=EndPos;i++)
printf("L[%d]=%d\n",i,arr[i]);
}
int main()
{
int i,n,L[N];
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&L[i]);
Quicksort(L,0,n-1);
Print(L,n-1);
}
上面采用了遞歸的方法來進行快速排序。快速排序是不穩定的。
這部分主要講解的是快速排序，下面還將繼續進行其余排序方法的說明。
