目录
堆排序
归并排序：
冒泡排序 ——> 快速排序：
冒泡排序：
* 归并排序的核心是两步： * 1、把数组分割成左右子树，递归，直到不能在分割为止； * 2、从最小子树 依次往上 逐层合并
public static void main(String[] args) { int[] arr = {1,2,5,4,6,5,8,7}; int[] temp = new int[8]; print("【原始数组】", arr); merge_sort(arr, 0, arr.length-1, temp); print("【归并排序】", temp); } /** * 递归 将数组分割成左右子树 * @param array * @param first * @param last * @param temp */ public static void merge_sort(int array[], int first, int last, int temp[]) { if (first < last) { int middle = (first + last) / 2; merge_sort(array, first, middle, temp);// 左半部分排好序 merge_sort(array, middle + 1, last, temp);// 右半部分排好序 mergeArray(array, first, middle, last, temp); // 合并左右部分 } } /** * 合并 ：将两个序列a[first-middle],a[middle+1-end]合并 * @param array 原始数组 * @param temp 临时存储排序成功的子数组，然后将子数组赋值给原始数组对应的部分 */ public static void mergeArray(int array[], int first, int middle, int last, int temp[]) { int begin = first; //子数组的起始索引 int point = middle; //子数组分割中点 int step = middle + 1; //子数组-右部分的起始点 int end = last; //子数组最后索引 int temp_index = 0; //定义 temp数组的index, 用于为temp数组赋值 while (begin <= point && step <= end) { //如果左子树和右子树都有元素 => 逐个比较添加进temp数组 if (array[begin] <= array[step]) { temp[temp_index] = array[begin]; temp_index++; begin++; } else { temp[temp_index] = array[step]; temp_index++; step++; } } while (begin <= point) { //左子树还没结束，右子树已经结束 temp[temp_index] = array[begin]; temp_index++; begin++; } while (step <= end) { //右子树没结束， 左子树已经结束 temp[temp_index] = array[step]; temp_index++; step++; } for (int ii = 0; ii < temp_index; ii++) { array[first + ii] = temp[ii]; } }快速排序——冒泡(交换)排序的改进——挖坑填空
随机取一个数作为key，将比key大的数放在右边，比key小的数放在左边
分成左右子数组 依次递归
public static void quickSort(int [] arr,int left,int right){ if(left>=right) { return; } int key = arr[left]; //选择第一个数为key int lIndex = left; //记录左移动的下标 int rIndex = right; //记录右移动的下标 while(lIndex < rIndex){ while(lIndex < rIndex && arr[rIndex] > key) { //从右向左 找小于key值 的索引 rIndex--; } if(lIndex < rIndex){ arr[lIndex] = arr[rIndex]; lIndex++; } while(lIndex < rIndex && arr[lIndex] < key) { //从左向右 找大于key值 的索引 lIndex++; } if(lIndex < rIndex){ arr[rIndex] = arr[lIndex]; rIndex--; } } arr[lIndex] = key; quickSort(arr, left, lIndex-1);//递归调用 quickSort(arr, lIndex+1, right);//递归调用 }
