排序
-
冒泡排序
从第零个元素开始，挨个比较相邻的右边元素，大于相邻元素则与它互换位置。注意设置一个标记变量flag初始为false，flag表示一趟冒泡中是否有元素交换，有则设为true。只要flag为false，则可以推定排序已经完成。
public static void main(String[] args) { int[] list = {1,2,3,4,10,5}; int len = list.length; boolean flag = false; //标记一趟排序后有没有发生交换 int temp; for (int j = 0; j < len-1; j++) { for (int i=0; i < len -j-1;i++){ if (list[i]>list[i+1]) { flag = true; temp = list[i]; list[i] = list[i+1]; list[i+1] = temp; } } if (!flag) { break; }else flag = false; System.out.printf("第%d次排序后的结果为%s\n",j,Arrays.toString(list)); } System.out.println("最后结果为："+Arrays.toString(list)); } -
选择排序
每轮选择最小值放前面
public static void sort(int[] array){ int minIndex=0; int min; int temp; int len =array.length; for (int i = 0; i < (len - 1); i++) { min = array[i]; for (int j=i+1;j<len;j++){ if ( array[j]<min){ min = array[j]; minIndex = j; //记录最小值下标 } } temp =array[i]; array[i] = array[minIndex]; array[minIndex] = temp; System.out.printf("第%d趟排序：%s\n",i, Arrays.toString(array)); } } -
插入排序
类似于打扑克牌插入一张牌。它维护一个有序数组，比如遍历到i时，数组[0,i-1]是有序的，要将nums[i]插入到合适位置（从后往前挨个比较，只要小于了前面的某个数，就插进去）。比较的时候如果不满足要求，需要将[0,i-1]中的相关元素往后移动一位，最后再插入nums[i]。核心代码为：
while (index >= 0 && array[i]<array[index]){ array[index+1] = array[index]; index--; } array[index+1] = temp;完整代码：
public static void sort02(int[] array){ //从后往前查找空位 int index; int len = array.length; for (int i = 1; i < len; i++) { //注意i是从1开始的 int temp = array[i]; index = i-1; while (index >= 0 && array[i]<array[index]){ array[index+1] = array[index]; index--; } array[index+1] = temp; System.out.printf("第%d次排序：%s\n",i, Arrays.toString(array)); } } -
希尔排序(Shell)
希尔排序就是对插入排序的优化，让数组逐步的部分有序，最后gap=1，变成插入排序。代码就是在插入排序基础上多了一层循环。
public static void sort(int[] array){ //shell排序是对插入排序的改进,变间隔的插入排序 int len =array.length; int temp; int gap = len/2; //为每组数据之间的间隔 while (gap>0){ for (int i = gap;i<len;i++ ){ //从gap开始 int index = i-gap; //记录待插入元素的索引 temp = array[i]; //待插入的元素 if (array[index+gap] < array[index]){ //判断待插入元素前是否已经有序 while (index>=0 && temp < array [index]){ array[index+gap] = array[index]; index -= gap; } array[index+gap] = temp; } } gap = gap/2; System.out.println(Arrays.toString(array)); } } -
归并排序(有点二叉树后序遍历的意思)
分治法的典型应用。先利用递归函数mergeSort()进行“分”，然后利用merge方法进行“合”。
mergeSort()方法如下：
//每一个mergesort（分）都有一个merge（合）方法 public static void mergeSort(int[] array,int left,int right){ int mid = (left+right)/2; //递归出口 if (left >= right){ return; } mergeSort(array,left,mid); //将左边分开 mergeSort(array,mid+1,right); //将数组右边分开 //最后把分好的两部分数组进行合并，形成一个数组 merge(array,left,mid,right); } merge()方法需要用到一个新数组来复制原来的数组，对复制好的新数组进行操作，把排序的结果逐步写到原数组之中。三个指针是关键 ，分别记录左边数组、右边数组、新数组的操作位置。
public static void merge(int[] array,int left,int mid,int right){ int[] temp = new int[right-left+1]; //新建一个数组和原数组长度一致 int indexTemp = 0; //新数组的指针，初始状态指向最左边 int s1 = left; //左边子数组的指针，初始指向左边 int s2 = mid +1; //右边子数组的指针，初始指向左边 while (s1 <= mid && s2 <= right){ if (array[s1] <= array[s2]){ temp[indexTemp] = array[s1]; s1++; indexTemp++; }else{ temp[indexTemp] = array[s2]; s2++; indexTemp++; } } //因为不知道是哪一边先操作完毕，因此需要两个while，把这两种情况都包含进去 while (s1<=mid){ temp[indexTemp] = array[s1]; s1++; indexTemp++; } while (s2<=right){ temp[indexTemp] = array[s2]; s2++; indexTemp++; } for (int i = 0; i < temp.length; i++) { array[i+left] = temp[i]; } } -
快速排序(类似于二叉树前序遍历)
先选出一个基准值key，代码里面是数组的最左侧值。然后定义两个哨兵，分别指向数组最左侧和最右侧。右侧哨兵从右往左找小于key的元素，左侧哨兵从左往右找大于key的元素。如果此时l<r，则交换左侧哨兵和右侧哨兵的元素。直到l=r，退出循环，然后让l=r处的元素等于key，最左侧元素为nums[r]。最后递归处理左侧和右侧。
public static void quickSort(int[] array, int left, int right) { if (array == null || array.length == 0){ //<--递 (1) return; // 归 } // 出 if (left>right) return; //<--口 (2) int key = array[left]; //中枢值 int l = left; //增加左右 int r = right; //两个哨兵 int temp; //临时变量用于交换 while (l < r) { while (l != r && array[r] >= key) { //从右往左扫描找到小于基准值key的一个元素 r--; } while (l != r && array[l] <= key) { //从左向右扫描找到大于基准值key的一个元素 l++; } if (l < r) { //交换小值与大值 temp = array[l]; array[l] = array[r]; array[r] = temp; } } //让最左侧元素等于r出元素，r处元素等于key array[left] = array[l]; array[l] = key; //递归处理key的左右两侧 quickSort(array, left, l - 1); quickSort(array, l + 1, right); } -
基数排序(桶排序)
先求出元素中的最大元素位数(将整数转化为字符串再求长度)。然后构造出十个桶，每个桶深arr.length。首先取元素的个位进行桶排序，将对应的元素丢入对应的桶中（个位元素是几，就丢入对应桶中），再从桶中取出各个元素排序，复制在原数组中。此过程循环到最高位。
public static void radixSort(int[] arr,int loopTime) { int len = arr.length; //初始化桶 int[][] bucket = new int[10][len]; //桶里面的元素计数器 int[] count = new int[10]; for (int i=0;i<loopTime;i++) { //将各个元素放入对应桶中 for (int value : arr) { int number = value / ((int) Math.pow(10, i)) % 10; bucket[number][count[number]] = value; count[number]++; } //从桶中取出各个元素 int n = 0; for (int k = 0; k < 10; k++) { if (count[k] != 0) { for (int m = 0; m < count[k]; m++) { arr[n] = bucket[k][m]; n++; } //计数器归零！！！ count[k] = 0; } } } } -
堆排序(优先队列)
分两步：
首先构造一个大顶堆自下而上进行构造(从最下方的非叶子结点一排开始)，选定元素后又从上至下进行调整。
然后才真正进行堆排序(交换首元素和尾元素，此时最大值在末尾，只需要让首元素下沉到合适位置就行)。
/** * * @param arr 要构造大顶堆的数组 * @param parent 进行构造的数组元素 * @param len 构造大顶堆的数组长度 */ public static void adjustHeap (int[] arr,int parent,int len) { int temp = arr[parent]; int child = 2*parent+1; while (child < len) { if (child+1<len && arr[child+1]>arr[child]) { child++; } if (arr[child] <= temp) { //说明找到插入temp的合适位置了 break; } arr[parent] = arr[child]; parent = child; child = child*2+1; } arr[parent] = temp; } public static void heapSort (int[] arr) { //构建大顶堆 for (int i=arr.length/2-1;i>=0;i--) {//从非叶子结点开始 adjustHeap(arr,i,arr.length); } // System.out.println(Arrays.toString(arr)); //进行堆排序 for (int i=arr.length-1;i>=0;i--) { int tmp = arr[i]; arr[i] = arr[0]; arr[0] = tmp; adjustHeap(arr,0,i); } } -
排序总结
内部排序：排序期间元素全部存放在内存中的排序；
外部排序：排序期间元素无法全部存放在内存中，必须在排序过程中根据要求不断地进行内外存之间移动地排序；
(这八种排序算法中除了多路归并排序是外部排序，其他都是内部排序)
稳定性：指的是经过排序后，值相同的元素保持原来顺序中的相对位置不变.
各算法时间复杂度、空间复杂度、所需辅助空间与稳定性如下：
