【Java】排序算法

2019-11-06 07:34:04

字体：大中小

来源：转载

供稿：网友

所有排序算法的基本原理无外乎将一个无序序列分为有序区（1个即有序）和无序区，然后不断重复迭代将无序区的数放入有序区。

以下排序算法皆以升序为例：

一、穷举法： 1.冒泡排序(Bubble Sort)：如图大数往上顶，任意两个相邻数从无序到有序。

这里写图片描述

PRivate static void BubbleSort(int[] array){ for(int i = 0;i < array.length - 1;i++) for(int j = 0;j < array.length - 1 - i;j++) if(array[j + 1] < array[j]){ int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } }

2.插入排序(Insertion Sort)：如图左侧为有序区，右侧无序区，将无序区的第一个元素插入到有序区合适的位置，重复过程。这里写图片描述

private static void InsertionSort(int[] array) { for (int i = 1; i < array.length; i++) { int j; int target = array[i]; for (j = i; j > 0 && target < array[j - 1];j--) { array[j] = array[j - 1]; } array[j] = target; } }

3.选择排序(Selection Sort)：如图左侧为有序区，右侧无序区。将无序区最小的元素与无序区的第一个元素对调，重复过程。这里写图片描述

private static void SelectionSort(int[] array) { //宏观上：将无序区最小的元素与第一个元素对调 for(int i = 0; i < array.length; i++) { //微观上：只要比基准元素小就与第一个元素对调 for(int j = i + 1; j < array.length; j++) { if(array[i] > array[j]) { int temp = array[j]; array[j] = array[i]; array[i] = temp; } } } }

二、分治法(Divide and Conquer)： 4.归并排序(Merge Sort)：这里写图片描述

//排序 private static void MergeSort(int[] array, int low, int high) { int mid = (low + high) / 2; if (low < high) { MergeSort(array, low, mid);// 左边 MergeSort(array, mid + 1, high);// 右边 Merge(array, low, mid, high);// 左右归并 } } //归并 private static void Merge(int[] array, int low, int mid, int high) { int[] tempArray = new int[high - low + 1]; int leftLow = low;// 左开头 int rightLow = mid + 1;// 右开头 int i = 0; //将两个要归并的数组按序一个一个地移入新数组，知道某个数组被掏空 while (leftLow <= mid && rightLow <= high) { if (array[leftLow] < array[rightLow]) { tempArray[i++] = array[leftLow++]; } else { tempArray[i++] = array[rightLow++]; } } // 把左边剩余的数移入数组 while (leftLow <= mid) { tempArray[i++] = array[leftLow++]; } // 把右边边剩余的数移入数组 while (rightLow <= high) { tempArray[i++] = array[rightLow++]; } // 把新数组中的数覆盖给array数组 for (int j = 0; j < tempArray.length; j++) { array[j + low] = tempArray[j]; } }

5.快速排序(Quick Sort)：随便找个基准数（一般取首或尾），小的放它左边，大的放它右边。对两侧的分区重复以上过程。其中的基准数就是有序区，两侧区间就是无序区。这里写图片描述

//返回分区后的中轴在序列中的位置 private static int getMiddle(int[] array, int low, int high) { int tmp = array[low]; //数组的第一个作为中轴 while (low < high) { //比中轴小的记录移到低端 while (low < high && array[high] > tmp) { high--; } array[low] = array[high]; //比中轴大的记录移到高端 while (low < high && array[low] < tmp) { low++; } array[high] = array[low]; } array[low] = tmp; //中轴记录到尾 return low; //返回中轴的位置(介于两个分区之间) } private static void QuickSort(int[] array, int low, int high) { if (low < high) { int middle = getMiddle(array, low, high); //将list数组进行一分为二 QuickSort(array, low, middle - 1); //对低字表进行递归排序 QuickSort(array, middle + 1, high); //对高字表进行递归排序 } }

上一篇：二、java-常用java验证码

下一篇：java之成绩总结