八、快速排序：
1.基本思想：
选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
2.实现过程：
32 , 13, 5, 32, 43
如图所示：
3.实现代码：
package cn.hz.demo2;
/** * @author hz * @version 1.0 * * 快速排序 * 需求分析： * 选择第一个数为p，小于p的数放在左边，大于p的数放在右边。 * 递归的将p左边和右边的数都按照第一步进行，直到不能递归。 * */public class Demo8 { public static void main(String[] args) { int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1}; //定义需要排序数组 System.out.println("快速排序前"); for (int ia:a){ System.out.print(ia+"t"); } //快速排序 quickSort(a,0,a.length-1); System.out.println("n快速排序后"); for (int ia:a){ System.out.print(ia+"t"); }
} public static void quickSort(int[] numbers, int start, int end) { if (start < end) { int base = numbers[start]; // 选定的基准值（第一个数值作为基准值） int temp; // 记录临时中间值 int i = start, j = end; do { while ((numbers[i] < base) && (i < end)) i++; while ((numbers[j] > base) && (j > start)) j--; if (i <= j) { temp = numbers[i]; numbers[i] = numbers[j]; numbers[j] = temp; i++; j--; } } while (i <= j); if (start < j) quickSort(numbers, start, j); if (end > i) quickSort(numbers, i, end); } }}
复制代码
实现效果：
4.分析：
快速排序是不稳定的排序。
快速排序的时间复杂度为 O(nlogn)。
当 n 较大时使用快排比较好，当序列基本有序时用快排反而不好。
5.稳定性总结：
快速排序有两个方向，左边的 i 下标一直往右走（当条件 a[i] <= a[center_index]时），其中 center_index 是中枢元素的数组下标，一般取为数组第 0 个元素。
而右边的 j 下标一直往左走（当 a[j] > a[center_index]时）。
如果 i 和 j 都走不动了，i <= j, 交换 a[i]和 a[j],重复上面的过程，直到 i>j。交换 a[j]和 a[center_index]，完成一趟快速排序。
在中枢元素和 a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11
现在中枢元素 5 和 3(第 5 个元素，下标从 1 开始计)交换就会把元素 3 的稳定性打乱。
所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和 a[j]交换的时刻。
九、归并排序：
1.基本思想：
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
2.实现过程：
3.实现代码：
package cn.hz.demo2;
/** * @author hz * @version 1.0 * * 归并排序 * 需求分析: * 选择相邻两个数组成一个有序序列。 * 选择相邻的两个有序序列组成一个有序序列。 * 重复第二步，直到全部组成一个有序序列。 */public class Demo9 { public static void main(String[] args) { int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8}; System.out.println("归并排序之前："); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } //归并排序 mergeSort(a,0,a.length-1); System.out.println(); System.out.println("排序之后："); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } } private static void mergeSort(int[] a, int left, int right) { if(left<right){ int middle = (left+right)/2; //对左边进行递归 mergeSort(a, left, middle); //对右边进行递归 mergeSort(a, middle+1, right); //合并 merge(a,left,middle,right); } }
private static void merge(int[] a, int left, int middle, int right) { int[] tmpArr = new int[a.length]; int mid = middle+1; //右边的起始位置 int tmp = left; int third = left; while(left<=middle && mid<=right){ //从两个数组中选取较小的数放入中间数组 if(a[left]<=a[mid]){ tmpArr[third++] = a[left++]; }else{ tmpArr[third++] = a[mid++]; } } //将剩余的部分放入中间数组 while(left<=middle){ tmpArr[third++] = a[left++]; } while(mid<=right){ tmpArr[third++] = a[mid++]; } //将中间数组复制回原数组 while(tmp<=right){ a[tmp] = tmpArr[tmp++]; } }}
复制代码
实现效果：
4.分析：
归并排序是稳定的排序方法。
归并排序的时间复杂度为 O(nlogn)。
速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列
5.稳定性总结：
归并排序是把序列递归地分成短序列，递归出口是短序列只有 1 个元素(认为直接有序)或者 2 个序列(1 次比较和交换)，
然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。
可以发现，在 1 个或 2 个元素时，1 个元素不会交换，2 个元素如果大小相等也没有人故意交换，这不会破坏稳定性。
那么，在短的有序序列合并的过程中，稳定是是否受到破坏？
没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。
所以，归并排序也是稳定的排序算法。
十、基数排序：
1.基本思想：
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
2.实现过程：
该排序方式比较麻烦，换一个值较多的数组进行讲解：
原数组值：
135， 242, 192， 93， 345， 11， 24， 19
第一轮比较：将所有的数的个位数取出，按照个位数进行排序，构成一个序列，结果如下：
11， 242， 192， 93， 24， 135， 345, 19
如图所示：
第二轮比较：将新构成的所有的数的十位数取出，按照十位数进行排序，构成一个序列，结果如下：
11, 19， 24， 135, 242，345， 192， 93
如图所示：
3.实现代码：
package cn.hz.demo2;
import java.util.ArrayList;import java.util.List;
/** * @author hz * @version 1.0 * * 基数排序 * 需求分析： * 将所有的数的个位数取出，按照个位数进行排序，构成一个序列。 * 将新构成的所有的数的十位数取出，按照十位数进行排序，构成一个序列。 */public class Demo10 { public static void main(String[] args) { int[] array={49,38,65,97,76,13,27,49,78,34,12,64,1,8}; System.out.println("基数排序之前："); for (int i = 0; i < array.length; i++) { System.out.print(array[i]+" "); } //基数排序 //首先确定排序的趟数; int max = array[0]; for (int i = 1; i < array.length; i++) { if (array[i] > max) { max = array[i]; } } int time = 0; //判断位数; while (max > 0) { max /= 10; time++; } //建立10个队列; List<ArrayList> queue = new ArrayList<ArrayList>(); for (int i = 0; i < 10; i++) { ArrayList<Integer> queue1 = new ArrayList<Integer>(); queue.add(queue1); } //进行time次分配和收集; for (int i = 0; i < time; i++) { //分配数组元素; for (int j = 0; j < array.length; j++) { //得到数字的第time+1位数; int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i); ArrayList<Integer> queue2 = queue.get(x); queue2.add(array[j]); queue.set(x, queue2); } int count = 0;//元素计数器; //收集队列元素; for (int k = 0; k < 10; k++) { while (queue.get(k).size() > 0) { ArrayList<Integer> queue3 = queue.get(k); array[count] = queue3.get(0); queue3.remove(0); count++; } } }
System.out.println("n基数排序之后："); for (int i = 0; i < array.length; i++) { System.out.print(array[i]+" "); }
}}
复制代码
实现效果：
4.分析：
基数排序是稳定的排序算法。
基数排序的时间复杂度为 O(d(n+r)),d 为位数，r 为基数。
5.稳定性总结：
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。
有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序结果就是高优先级高的在前，高优先级相同的情况下低优先级高的在前。
基数排序基于分别排序，分别收集，所以其是稳定的排序算法。
总结:
1.稳定性：
稳定：冒泡排序、插入排序、归并排序和基数排序
不稳定：选择排序、快速排序、希尔排序、堆排序
2.平均时间复杂度：
O(n^2):直接插入排序，简单选择排序，冒泡排序。
在数据规模较小时（9W 内），直接插入排序，简单选择排序差不多。当数据较大时，冒泡排序算法的时间代价最高。性能为 O(n^2)的算法基本上是相邻元素进行比较，基本上都是稳定的。
O(nlogn):快速排序，归并排序，希尔排序，堆排序。
其中，快排是最好的， 其次是归并和希尔，堆排序在数据量很大时效果明显。
3.排序算法的选择：
规模较小：
数据规模不是很大：
数据规模很大：
对稳定性有求，则可考虑归并排序。
对稳定性没要求，宜用堆排序
序列初始基本有序（正序），宜用直接插入，冒泡。
评论