快速排序

浏览数：57 / 时间：2015年06月08日

快速排序算法

　　一、基本思想：在待排序的 n 个记录中任取一个记录(通常取第一个记录)，把该记录放入适当的位置后，数据序列被此记录划分为两部分，所有的关键字比该记录小的放在前部分、大的放置在后部分，并将该记录排在这两部分的中间，以此类推，直至所有的记录排序完成。

　　技术分享　　

　　二、C 语言代码：

 1 //对 R[s] 至 R[t] 的元素进行快速排序 
 2 void quickSort(RecType R[], int s, int t)
 3 {
 4     int i = s;
 5     int j = t;
 6     RecType tmp;
 7     
 8     if (s < t) {
 9         tmp = R[s]; //选定区间第一个元素作为基准 
10         
11         //从区间两端交替向中间扫描, 直至 i = j 为止 
12         while (i != j) {
13             while (j > i && R[j].key > tmp.key) { //从右向左扫描
14                 j--;
15             }
16             R[i] = R[j]; //将遍历寻找到的第一个 R[j].key 小于 tmp.key 的值进行交换
17             i++; 
18             while (i < j && R[i].key < tmp.key) {
19                 i++;
20             }
21             R[j] = R[i];
22             j--;
23         } 
24         R[i] = tmp;
25         quickSort(R, s, i-1); //对左区间递归排序 
26         quickSort(R, i+1, t); //对右区间递归排序 
27     }
28 }