3、代码实现
//插入排序 public static void insertSort(int[] arr ){ int insertVal = 0; int insertIndex = 0; for (int i = 1; i < arr.length; i++) { //定义待插入的数 insertVal = arr[i]; // 即arr[i]的前面这个数的下标 insertIndex = i - 1; // 给insertVal 找到插入的位置 // 说明 // 1. insertIndex >= 0 保证在给insertVal 找插入位置，不越界 // 2. insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置 // 3. 就需要将 arr[insertIndex] 后移 while(insertIndex >= 0 && insertVal < arr[insertIndex]){ arr[insertIndex+1] = arr[insertIndex]; insertIndex–; } // 当退出while循环时，说明插入的位置找到, insertIndex + 1 if(insertIndex + 1 != i){ arr[insertIndex+1] = insertVal; } } }
4、速度测试
插入排序：120000数据，1秒
（四）希尔排序
1、基本思想
希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法也是冲破O(n²)的第一批算法之一。它与插入排序的不同之处在于，它会优先比较较远的元素。
2、效果图
3、代码实例
希尔排序有两种方式。
①希尔排序（冒泡排序）
//希尔排序 // 使用逐步推导的方式来编写希尔排序 // 希尔排序时， 对有序序列在插入时采用交换法, // 思路(算法) ===> 代码 public static void shellSort(int[] arr){ // 根据前面的逐步分析，使用循环处理 for(int step = arr.length/2;step>0;step /= 2 ){ for (int i = step; i < arr.length; i++) { // 遍历各组中所有的元素(共step组，每组有个元素), 步长step for (int j = i - step; j >= 0; j -= step) { // 如果当前元素大于加上步长后的那个元素，说明交换 if (arr[j] > arr[j + step]) { int temp = arr[j]; arr[j] = arr[j + step]; arr[j + step] = temp; } } } } }
速度测试：
冒泡法希尔排序：120000数据，11秒
②希尔排序（插入排序）
//对交换式的希尔排序进行优化->插入法 public static void shellSort2(int[] arr) { // 增量step, 并逐步的缩小增量 for (int step = arr.length / 2; step > 0; step /= 2) { // 从第step个元素，逐个对其所在的组进行直接插入排序 for (int i = step; i < arr.length; i++) { int j = i; int temp = arr[j]; if(arr[j]<arr[j-step]){ while (j - step >= 0&&temp<arr[j-step]){ arr[j] = arr[j-step]; j -= step; } arr[j] = temp; } } }
速度测试：
插入法希尔排序：12000000数据，4秒，叹为观止
（五）快速排序
1、基本思想
通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录进行排序，以达到整个排序的过程。
2、效果图
3、算法描述
- 快速排序使用分治法把一个串分为两个子串；
- 找一个基准点，暂时选中间点为基准点；
- 重新排序数列，比基准值小的放在基准点前面，大的放在后面；
- 递归的把小于基准值的子数列和大于基准值的子数列排序；
4、代码实例
//快速排序 public static void quickSort(int[] arr,int left, int right) { int l = left; //左下标 int r = right; //右下标 //pivot 中轴值 int pivot = arr[(left + right) / 2]; int temp = 0; //临时变量，作为交换时使用 //while循环的目的是让比pivot 值小放到左边 //比pivot 值大放到右边 while( l < r) { //在pivot的左边一直找,找到大于等于pivot值,才退出 while( arr[l] < pivot) { l += 1; } //在pivot的右边一直找,找到小于等于pivot值,才退出 while(arr[r] > pivot) { r -= 1; } //如果l >= r说明pivot 的左右两的值，已经按照左边全部是 //小于等于pivot值，右边全部是大于等于pivot值 if( l >= r) { break; } //交换 temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; //如果交换完后，发现这个arr[l] == pivot值 相等 r–， 前移 if(arr[l] == pivot) { r -= 1; } //如果交换完后，发现这个arr[r] == pivot值 相等 l++， 后移 if(arr[r] == pivot) { l += 1; } } // 如果 l == r, 必须l++, r–, 否则为出现栈溢出 if (l == r) { l += 1; r -= 1; } //向左递归 if(left < r) { quickSort(arr, left, r); } //向右递归 if(right > l) { quickSort(arr, l, right); } }
5、速度测试
快速排序：12000000数据，1秒，逆天而行
（六）归并排序
1、基本思想
归并排序采用经典的分治策略，分治法将问题分成一些小的问题然后递归解决，则治的阶段就是将分的阶段得到的答案修补在一起，即分而治之。
2、效果图
3、代码实现
//归并排序 public static void mergerSort(int[] arr,int left,int right,int[] temp){ if(left<right){ //中间索引 int middle = (left + right)/2; //向左递归进行分解 mergerSort(arr,left,middle,temp); //向右递归进行分解 mergerSort(arr,middle + 1,right,temp); //合并 merger(arr, left, middle, right, temp); } } //合并 public static void merger(int[] arr,int left,int middle,int right,int[] temp){ int i = left; // 初始化i, 左边有序序列的初始索引 int j = middle + 1; //初始化j, 右边有序序列的初始索引
