排序算法-【Java实现】-【桶、冒泡、快速、归并、插入排序】
排序算法演示地址：https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
桶排序
顾名思义，将数组分到有限数量的桶子里。如下图：
定义一个桶的数组，将每个元素的值对应桶的下标存入，并将值加一，存完后从头开始往出取，每取一个值减一。
代码实现：
public static void bucketSort(int[] nums) {
int max = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] > max) {
max = nums[i];
}
}
int[] temps = new int[max + 1];
for (int num : nums) {
temps[num]++;
}
int count = 0;
for (int i = 0; i < temps.length; i++) {
while (temps[i] != 0) {
nums[count] = i;
temps[i]--;
count++;
}
}
}
public static void main(String[] args) {
int[] nums = {6,1,2,7,9,3,4,5,0,8};
System.out.println("排序前：" + Arrays.toString(nums));
bucketSort(nums);
System.out.println("排序后：" + Arrays.toString(nums));
}
缺点就是当数值太大时浪费空间，时间复杂度为O(M+N)。
复杂的桶排序：（演示地址：https://www.cs.usfca.edu/~galles/visualization/BucketSort.html）
冒泡排序
重复地走扫描要排序的元素列，依次比较两个相邻的元素，如果顺序错误就把他们交换过来。
动画演示：
代码实现：
public static void bubbleSort(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
for (int j = 0; j < nums.length - 1 - i; j++) {
if (nums[j] > nums[j+1]) {
nums[j] = nums[j] ^ nums[j+1];
nums[j+1] = nums[j] ^ nums[j+1];
nums[j] = nums[j] ^ nums[j+1];
}
}
}
}
public static void main(String[] args) {
int[] nums = {6,1,2,7,9,3,4,5,0,8};
System.out.println("排序前：" + Arrays.toString(nums));
bubbleSort(nums);
System.out.println("排序后：" + Arrays.toString(nums));
}
快速排序
动画演示：
代码实现：
/**
* 快速排序
* @param left 左指针 初始值为0
* @param right 右指针 初始值为数组长度-1
* @param nums 排序数组
*/
public static void quickSort(int left, int right,int[] nums) {
if (left >= right) {
return;
}
//基准数
int temp = nums[left];
int i = left;
int j = right;
while (i < j) {
//要先从右往左找
while (nums[j] >= temp && i < j) {
j--;
}
//再从左往右找
while (nums[i] <= temp && i < j) {
i++;
}
//交换
if (i < j) {
nums[i] = nums[i] ^ nums[j];
nums[j] = nums[i] ^ nums[j];
nums[i] = nums[i] ^ nums[j];
}
}
//基准数换位
nums[left] = nums[i];
nums[i] = temp;
//分别递归基准数两边的序列
quickSort(left,i-1,nums);
quickSort(i+1,right,nums);
}
public static void main(String[] args) {
int[] nums = {6,1,2,7,9,3,4,5,0,8};
System.out.println("排序前：" + Arrays.toString(nums));
quickSort(0,nums.length-1,nums);
System.out.println("排序后：" + Arrays.toString(nums));
}
归并排序
归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
动画演示：
代码实现：
/**
* 归并排序
* @param l 初始值为0
* @param h 初始值为数组长度-1
* @param nums 排序前数组
* @return 排序后数组
*/
public static int[] mergeSort(int l, int h,int[] nums) {
if (l == h) {
return new int[]{nums[l]};
}
int mid = l + (h - l) / 2;
//左有序数组
int[] leftArr = mergeSort(l, mid, nums);
//右有序数组
int[] rightArr = mergeSort(mid + 1, h, nums);
//新有序数组
int[] newNum = new int[leftArr.length + rightArr.length];
int m = 0, i = 0, j = 0;
while (i < leftArr.length && j < rightArr.length) {
newNum[m++] = leftArr[i] <= rightArr[j] ? leftArr[i++] : rightArr[j++];
}
while (i < leftArr.length) {
newNum[m++] = leftArr[i++];
}
while (j < rightArr.length) {
newNum[m++] = rightArr[j++];
}
return newNum;
}
public static void main(String[] args) {
int[] nums = {6,1,2,7,9,3,4,5,0,8};
System.out.println("排序前：" + Arrays.toString(nums));
System.out.println("排序后：" + Arrays.toString(mergeSort(0, nums.length - 1, nums)));
}
插入排序
对于少量元素的排序，它是一个有效的算法 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。
动画演示：
代码实现：
public static void insertionSort(int[] nums) {
for (int i = 1; i < nums.length; i++) {
int j = i;
while (j >= 1) {
if (nums[j] < nums[j-1]) {
nums[j] = nums[j] ^ nums[j-1];
nums[j-1] = nums[j] ^ nums[j-1];
nums[j] = nums[j] ^ nums[j-1];
}
j--;
}
}
}
public static void main(String[] args) {
int[] nums = {6,1,2,7,9,3,4,5,0,8};
System.out.println("排序前：" + Arrays.toString(nums));
insertionSort(nums);
System.out.println("排序后：" + Arrays.toString(nums));
}