- 排序算法总结(图片CV的)
- 快速排序
基本思想:分而治之、挖坑填数
基本实现原理如下
- 首先选取target目标作为参考数字
- 然后将数组中所有的数据与target比较,比target小的置于左边,比target大的,置于右边,形成两个区间。
- 重复1、2步,直到数组的所有子区间的大小为1为止
- 例子如下:
- 设存在数组为[30,40,60,10,20,50],取第0个元素为target元素
- 伪代码描述如下:
- 设置初始参考值为target=arr[0],设置两个指针left=0,right=arr.length-1
- right--移动右边界索引,直到出现arr[right]<target时,此时填坑将arr[left]=arr[right],然后left++
- left++移动左边界索引,直达出现arr[left]>target时,此时填坑将arr[right]=arr[left],然后right--
- 重复b,c操作,直到left==right,将arr[left]=target
- 代码如下:
/** * @param arr 待排序数组 * @param left 左边界,一般是0 * @param right 右边界,一般是arr.length-1 */ public static void quickSort(int[] arr, int left, int right) { if (left < right) { int l = left, r = right, target = arr[left];//如果设置target在左边,则必须保证从right开始搜索 while (l < r) { while (l < r && arr[r] > target) r--;//从target相反方向(右边)搜索第一个小于target的 if (l < r) arr[l++] = arr[r]; while (l < r && arr[l] < target) l++;//从target相同方向搜索第一个大于target的 if (l < r) arr[r--] = arr[l]; } arr[l] = target;//填坑 quickSort(arr, left, l - 1); quickSort(arr, l + 1, right); } }
- 归并排序
基本思想:分而治之,先拆开后合并,由局部子序列有序推导出序列整体有序
基本实现原理如下
- 首先将需要排序的数组每次都对半拆分,直到每个序列都只有一个元素
- 而后进行合并操作,将arr[left...mid],arr[mid+1...right]合并
- 合并过程中,将arr[left...mid],arr[mid+1...right]每个元素进行比较,按照递增或者递减顺序存放进newArr
- 重复以上2、3步骤,直到到达递归树顶层
- 具体过程如下:
- 数组分组
- 数组治理
- 数组合并过程
- 归并排序代码
/** * 归并排序 * * @param arr * @param left * @param right * @return */ public static int[] MergeSort(int[] arr, int left, int right) { //递归树最底层,也就是递归出口 if (left == right) return new int[]{arr[left]}; //递归划分局部区间 int middle = (left + right) / 2; int[] leftNums = MergeSort(arr, left, middle);//分割左区间 int[] rightNums = MergeSort(arr, middle + 1, right);//分割右区间 //构建结果集 int[] temp = new int[leftNums.length + rightNums.length]; int l = 0, r = 0, m = 0; while (l < leftNums.length && r < rightNums.length) { //对temp[l]以及temp[r]比较,构建有序序列 //如果leftNums[l]>rightNums[r],则temp[m]=rightNums[r];然后temp++,r++ temp[m] = leftNums[l] > rightNums[r] ? rightNums[r++] : leftNums[l++]; m++; } //对于剩余的待比较序列进行排序 while (l < leftNums.length) { temp[m] = leftNums[l]; m++; l++; } while (r < rightNums.length) { temp[m] = rightNums[r]; m++; r++; } return temp; } • Shell排序
基本思想：增量逐渐缩小
基本实现原理如下
- 首先取target=arr.length/2为参考增量,每次将target减半
- 由arr[i]与arr[i-target]比较,若i-target大于i,则i-target后移
- 重复1、2操作,直至target=1
- shell排序过程
- 具体实现代码如下:
/** * 希尔排序 * * @param arr */ public static void shellSort(int[] arr) { int target = arr.length; //arr的数字匹配距离 for (int i = target / 2; i > 0; i = i / 2) { //分组数字配对 for (int j = 0; j < i; j++) { for (int k = j + i; k < target; k = k + i) { //如果arr[k-i]>arr[k],则arr[k-i]后面的数据全部后移 if (arr[k - i] > arr[k]) { int temp = arr[k]; //以i为距离,寻找同组数据 int index = k - i; while (index >= 0 && arr[index] > temp) { arr[index + i] = arr[index]; //改变距离 index = index - i; } //填坑 arr[index + i] = temp; } } } } }
