交换排序
交换排序的基本思想是：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。
6.3.1 冒泡排序
首先来看著名的交换排序算法：冒泡法。冒泡法的排序思想是：从第n个元素(a[n-1])开始，扫描数组，比较相邻两个元素，如果次序相反则交换。如此反复，直到没有任何两个违反相反原则的元素
假如待排数据为：9,6,2,3,10，那么每趟冒泡排序之后（从小到大），数据的变化情况为：
2,9,6,3,10
2,3,9,6,10
2,3,6,9,10
2,3,6,9,10
冒泡排序的算法如下：
void bubble_sort(int a[], int n){
int i, j, tmp;
for (i = 0; i < n-1; i++) {
for (j = n-1; j >= i+1; j--){
if (a[j] < a[j-1]){
tmp = a[j];
a[j] = a[j-1];
a[j-1] = tmp;
}
}
}
}
冒泡排序的时间复杂度为O(n^2)，它是稳定排序。
6.3.2 快速排序
快速排序的思想是：在当前无序区R[1..H]中任取一个数据元素作为比较的“基准”(不妨记为X，R[1])，用此基准将当前无序区划分为左右两个较小的无序区：R[1..I-1]和R[I+1..H]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R[1..I-1]≤X≤R[I+ 1..H](1≤I≤H)，当R[1..I-1]和R[I+1..H]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。
找一个数X（比如头一个元素）做基准，右边比X小的移动到左边，左边比X大的移动到右边，最后空出的位置就是X自己的位置
快速排序的时间复杂度为O(nlogn)，最坏情况为O(n^2)。对于大的、乱数序列一般相信是最快的已知排序。待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到O(n)的时间复杂度，而对于快速排序而言，这是最不好的情况。对于很小的数组（如N<=20），快速排序不如插入排序好。
void quickSort(int a[],int left,int right){
int i,j,temp;
i=left;
j=right;
temp=a[left];
if(left>right)
return;
while(i<j){
while(a[j]>=temp && j>i)
j--;
if(j>i)
a[i++]=a[j];
while(a[i]<=temp && j>i)
i++;
if(j>i)
a[j--]=a[i];
}
a[i]=temp;
quickSort(a,left,i-1);/*递归左边*/
quickSort(a,i+1,right);/*递归右边*/
}
void qsort(int a[], int n){
quickSort(a, 0, n-1);
}
typedef struct _data {
int low;
int high;
}DATA;
#define MAX 100
void quick_sort(int a[], int low, int high) {
DATA stack[MAX]={0};
int top = 0;
stack[0].low = low;
stack[0].high = high;
while(top>=0){
int l = stack[top].low;
int i = stack[top].low;
int j = stack[top].high;
int h = stack[top].high;
top--;
if(i>=j) {
continue;
}
int tmp = a[i];
while(i<j) {
while(a[j]>=tmp&&i<j) {
j--;
}
if(i<j) {
a[i] = a[j];
i++;
}
while(a[i]<=tmp&&i<j) {
i++;
}
if(i<j) {
a[j]=a[i];
j--;
}
}
a[i]=tmp;
DATA data;
data.low = l;
data.high = i-1;
if(top<MAX){
top++;
stack[top] = data;
}
data.low = i+1;
data.high = h;
if(top<MAX) {
top++;
stack[top] = data;
}
}
}
