①冒泡排序
描述：交换排序中最简单的排序方法。
生活例子：水中的气泡，体积大的先浮上来
基本思想：前无序，后有序，从头相邻比较，不断挤压向后冒泡。
排序过程：①整个待排序区分为无序区和有序区，初始有序区为空，无序区包括所有。
②从无序区第一个开始，并与相邻关键码比较，大于则交换，小则继续后移。
③重复②操作。
void BubbleSort(int r[], int n){ int temp, exchange; exchange = n; //先获取整个待排序序列所有记录 while(exchange != 0) { bound = exchange; //获得最后交换位置，因为该位置后的所有都在有序区 exchange = 0; //记录交换位置 for (int i = 1; i < bound; i++) { if (r[i] > r[i+1]){ /***进行交换***/ temp = r[i]; r[i] = r[i+1]; r[i+1] = temp; exchange = i; //记录每一次交换的位置 } } }}
排序过程：①整个待排序区分为无序区和有序区，初始有序区为空，无序区包括所有。
②从无序区第一个开始，并与相邻关键码比较，大于则交换，小则继续后移。
③重复②操作。
复杂度分析：最好的情况下，在一个循环内为正序，只需执行一次，比较了 n-1次，时间复杂度为 O(n)。
O(n2)。
平均的情况下：时间复杂度为： O(n2)。
②快速排序(分区交换排序)
描述：对起泡排序的改进，记录比较和移动向两端进行，关键码较大的移到后面，反之。
过程：①初始化，选第一个作为轴值，并将i，j分别指向最左右侧位置
②右侧扫描，将轴值记录与j 指向的记录进行比较，如果 j 指向的大，则 j--，重复扫描，直到j(右侧)记录小，将轴值记录与 j位置记录交换，i++
③左侧扫面，轴值与i 位置比较，i小则 i++,重复左侧扫描，直到 i大，将轴值与 i 位置记录交换，j--。
④重复②③直到i，j相同。
代码如下：
int Partition(int r[ ], int first, int end) { i=first; j=end; //初始化 while (i<j) { while (i<j && r[i]<= r[j]) j--; //右侧扫描 if (i<j) { r[i]←→r[j]; //将较小记录交换到前面 i++; } while (i<j && r[i]<= r[j]) i++; //左侧扫描 if (i<j) { r[j]←→r[i]; //将较大记录交换到后面 j--; } } retutn i; //i为轴值记录的最终位置 }
然后是对子序列递归
void QuickSort(int r[], int first, int end) { if(first < end) { pivot = Partition(r, first, end); QuickSort(r, first, pivot - 1); QuickSort(r, pivot + 1, end); }}
复杂度分析：最好的情况下，每次划分对一个记录定位后，该记录的左右子侧长度相等，为O(n)
最坏的情况下：待排序记录正序或逆序，O(n2)
平均：O(log2n)