线性表的交换排序

基于交换排序算法有两种：冒泡排序和快速排序 示例数组：int keys[] = new int[]{32,26,87,72,26,17};

冒泡排序

比较相邻两个元素，大的往后排。最简单的一个排序方法了。

public static void bubbleSort(int[] a) { int temp = 0; boolean exchange = true; for (int i = a.length - 1; i > 0&&exchange; --i) { exchange =false; for (int j = 0; j < i; ++j) { if (a[j]>a[j+1]) { exchange = true; temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } } } } 最好情况，数据排列有序，只需要一趟扫描，比较n次，没有数据移动，时间复杂度为O（n）（因为那个flag的存在，如果扫描一圈一个值都没有改变，证明本来就是有序的，无需再次扫描，循环结束，算法结束）最坏情况，数据序列随机排序和反序排列，需要n-1趟扫描，比较次数和移动次数都是O（n²）空间复杂度需要一个元素交换两个元素，空间复杂度为O（1）冒泡排序是稳定的

快速排序

以上面的示例数组32,26,87,72,26,17为例，我们发现，当我们第一次 把87下沉的时候87和72交换一次，其中有一次到达了temp位置，87和26又交换一次，到达temp位置，87又和17交换了一次，到达了temp位置，到达又离开，存在重复的数据移动，为了尽可能的避免这种事情的发生于是出现了快速排序。算法描述{36,36,97,75,61,19,26,49}：

选取序列的第一个元素keys[i]38作为基准值vot，空出keys[i]的值在序列后端寻找一个小于基准值的元素，交换到序列前端。即比较keys[j]元素26与基准值的大小。若小则将keys[j]元素26移动到keys[i]位置，i++，此时keys[j]位置空出在序列前端寻找大于基准值的元素，交换到序列后端。再比较keys[i]元素97与基准值，若大则将keys[i]元素97移动到序列后端的keys[j]位置，j–，keys[i]位置空出。不移动与基准值相等的元素重复执行2,3步骤。直到i==j，表示序列中的每一个元素都与基准值比较过了。并且已经将小于基准值的元素移动到前端，将大于基准值的元素移动到了后端。当前i（j）的位置则是基准值的最终位置。一趟快速排序将数据序列划分为两个子序列，范围分别为begin~j-1，i+1~end。每个子序列较短，再对两个子序列分别进行快速排序，直到子序列长度为1。看下面的图，图选的是最后一个为基准。 private static void quickSort(int[] keys,int begin,int end) { if (begin<end) { int i=begin,j=end,vot=keys[i]; while(i!=j){ while (i<j&&keys[j]>=vot) {//从后向前寻找较小值,不移动与基准值相同的值 j--; } if (i<j) { keys[i++] = keys[j];//子序列后端较小元素向前移动，等同于keys[i] = keys[j];i++; } while (i<j&&keys[i]<=vot) {//从前向后寻找较大值，不移动与基准值相等元素 i++; } if (i<j) { keys[j--] = keys[i];//子序列前端较大值向后移动 } } keys[i] = vot;//基准值到达最终位置 quickSort(keys,begin,j-1); quickSort(keys,i+1,end); } } 时间复杂度 最好情况 每趟排序将序列分成长度最近的两个子序列，时间复杂度为O(n*log₂ⁿ)最坏情况 每趟排序将序列分成长度差异很大的两个子序列，时间复杂度为O(n²)空间复杂度 递归调用需要使用栈来保存参数，栈所占用的空间与递归调用的次数有关，空间复杂度O(n*log₂ⁿ)~O(n)当n较大而且数据序列随机排列的时候，快速排序是快速的，当n很小或者基准值轩却不合适的时候，快速排序则较慢快速排序是不稳定排序