排 序
排序方法：
（1）插入排序
（2）交换排序
（3）选择排序
（4）归并排序
（5）基数排序
培训详细：
以插入排序、交换排序为例，对排序思想进行具体分析，以及对代码的解读。争取让大家读懂并且理解具体代码的作用。
插入排序
基本思想：每一趟将一个待排序的记录，按其关键字的大小插入到已经排好序的一组记录的适当位置上，直到所有待排序记录全部插入为止。
1. 直接插入排序
基本代码：
* void insert_order(int a[], intn, int key)
* {
* int i;
* for (i = n-1; i >= 0; i--)
* {
* if (key < a[i])
* a[i+1] = a[i];
* else
* break;
* }
* a[i+1] = key;
* }
* void sort_insert(int a[], intn)
* {
* int i;
* for (i = 1; i < n; i++)
* insert_order(a, i, a[i]);
* }
2. 折半插入排序
基本代码：
* void insert_order(int a[], intn, int key)
* {
* int m;
* int i;
* int low = 0;
* int high = n - 1;
* while(low <= high)
* {
* m = (low+high)/2;
* if(key < a[m])
* high = m-1;
* else
* low = m+1;
* }
* for (i = n-1; i > high; i--)
* a[i+1] = a[i];
* a[high+1] = key;
* }
* void sort_insert(int a[], intn)
* {
* int i;
* for (i = 1; i < n; i++)
* insert_order(a,i, a[i]);
* }
交换排序：
基本思想：两两比较待排序记录的关键字，一旦发现两个记录不满足次序要求时则进行排序，知道整个序列全部满足要求为止。
1. 冒泡排序bubble_sort
常规代码：
* void bubble_sort(int a[], intn)
* {
* int i;
* int j;
* int temp;
* for (i = 0; i
* {
* for (j = 0; j
* {
* if (a[j] > a[j+1])
* {
* temp = a[j];
* a[j] = a[j+1];
* a[j+1] = temp;
* }
* }
* }
* }
改进版冒泡：
* void bubble_sort(int a[], intn)
* {
* int i; int j; int flag = 1; int temp;
* for (i = 0; i
* {
* flag = 0;
* //flag置为0，如果本趟排序没有发生变化，则不会执行下趟排序
* for (j = 0; j < n-i-1; j++)
* {
* if (a[j]> a[j+1])
* {
* flag= 1;
* temp = a[j]; a[j] = a[j+1]; a[j+1] = temp;
* }
* }
* }
* }
2. 快速排序
方法一：
* int quickSort(int a[], int p,int r)
* {
* int i, j; int q; int temp; i = p-1;
* if(p > r) return 0;
* for(j = p; j < r; j++)
* {
* if(a[j] < a[r])
* {
* temp = a[j]; a[j] = a[i+1]; a[i+1] = temp;
* i++;
* }
* }
* temp = a[i+1]; a[i+1] = a[r]; a[r] = temp;
* q = i+1;
* quickSort(a, p, q-1);
* quickSort(a, q+1, r);
* }
方法二：
* int Partition(int a[], int low,int high)
* {
* int pivotkey;
*
* pivotkey = a[low];
* while (low < high)
* {
* while (low < high && pivotkey <= a[high])
* {
* --high;
* }
* a[low] = a[high];
*
* while (low < high && pivotkey >= a[low])
* {
* ++low;
* }
* a[high] = a[low];
* }
*
* a[low] = pivotkey;
* return low; //返回关键字的坐标
* }
*
* void quickSort(int a[], intlow, int high)
* {
* int pivotloc;
*
* if (low < high)
* {
* pivotloc = Partition(a, low, high); //接收关键字的位置
* quickSort(a, low, pivotloc-1);
* quickSort(a, pivotloc+1, high);
* }
* }