1.冒泡排序：冒泡排序算法是从最下面的记录开始,对每两个相邻的关键字进行比较,且使关键字较小的记录换至关键字较大的记录之上,使得经过一趟冒泡排序后,关键字最小的记录到达最上端,接着,再在剩下的记录中找关键字次小的记录,并把它换在第二个位置上。依次类推,一直到所有记录都有序为止。最小的数就如同水泡一样向上漂浮到水面，故谓之冒泡排序。
冒泡排序的改进：在有些情况下,在第i(i＜n-1)趟时已排好序了,但仍执行后面几趟的比较。实际上,一旦算法中某一趟比较时不出现记录交换,说明已排好序了,就可以结束本算法。所以可以设置一个标志位，一旦不出现记录交换，则跳出循环比较。
代码和下面的快速排序在一起。
2.快速排序：在快速排序中，我们将序列分成两个子序列，再对子序列进行快速排序，并递归直到序列排序完成。
步骤：(1)在序列中选择一个记录作为枢轴，通常是第一个；
(2)所有关键字比该记录关键字小的记录放置在前一部分,所有比它大的记录放置在后一部分,并把该记录排在这两部分的中间,这个过程称为快速排序；
(3)对子序列递归快速排序，直到按从小到大排列完成。
举例： S:6 8 7 9 0 1 3 2 4 5
【6】 5 4 2 3 0 1 6 9 7 8(这一步中，取6作为枢轴，i,j指针分别表示左边右边的第一个元素，从右开始比较5<6,S[0]=5；8>6，S[1]和S[9]交换位置；4<6,S[8]和S[2]交换位置....不一一叙说了)
接下来分为两个子序列5 4 2 3 0 1和9 7 8，再对其快速排序，一直递归直到排序完成。
改进冒泡排序代码和快速排序代码如下：(unix环境 2011-02-12)
#include <stdio.h> #include <stdlib.h> void BubbleSort(int a[], int len)//冒泡排序 { int i ,j , temp, exchange; for(j = 0; j < len; j++) { exchange = 0;//代表是否需要交换 for(i = len-1; i > j; i--) { if(a[i] < a[i-1]) { temp = a[i]; a[i] = a[i-1]; a[i-1] = temp; exchange = 1; } } if(exchange == 0)//为0时，没有记录交换，说明已完成冒泡排序 return; } } void print (int a[], int len) { int i; for(i = 0; i < len; i++) printf("%d/n",a[i]); } void QuickSort(int b[], int s, int len) { int i, j,temp; i = s; j = len-1; if(s < len-1)//子序列要至少存在一个元素 { temp = b[s]; while(i != j)//从两端向中间扫描，直到i=j { while(i<j && b[j] > temp) { j--; } if(i<j && b[j] < temp)//出现交换位置的条件 { b[i] = b[j]; i++; } while(i<j && b[i]< temp) { i++; } if(i<j && b[i] > temp)//出现交换位置的条件 { b[j] = b[i]; j--; } } b[i]=temp; QuickSort(b,0,i-1);//对左边子序列递归快速排序 QuickSort(b,i+1,len);//对右边子序列进行递归快速排序 } } int main(int argc, char *argv[]) { int len_a,len_b; int a[] = {9,8,7,6,5,4,3,2,1,0}; int b[] = {16,28,37,19,10,91,23,12,4,5}; len_a = sizeof(a)/sizeof(int); len_b = sizeof(b)/sizeof(int); BubbleSort(a, len_a); print(a, len_a); printf("next is the result of QuickSort:/n"); QuickSort(b, 0, len_b); print(b,len_b); return 0; }
