排序算法详解（二）

前面说了排序算法中的插入排序，下面就来看下排序中的快速排序。

在快速排序中，最简单的就是大家耳熟能详的冒泡排序，那么到底什么是冒泡排序呢？冒泡排序的思想就是：首先将第一个元素与第二个元素进行比较，若未逆序，则将两个元素的位置进行交换，然后继续比较第二个和第三个元素之间的大小，依此类推，知道第n-1个元素和第n个元素比较完成了以后，第一趟冒泡排序就终止了，它将最大的元素安置到了序列的最后，然后在进行第二趟冒泡排序，对前n-1个元素进行冒泡排序，然后将最大值放入n-1的位置上，以此类推，逐趟进行序列的遍历，而整个排序过程的结束就是在一趟排序中，没有元素进行交换。

下面就是一个使用冒泡排序的一个小例子：

#include<stdio.h>#include<stdlib.h>#define N 100void 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);}

上面采用了递归的方法来进行快速排序。快速排序是不稳定的。

这部分主要讲解的是快速排序，下面还将继续进行其余排序方法的说明。