归并排序
归并排序归并排序（Merge Sort）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序算法，平均时间复杂度为O(nlogn)。
基本思想
- 将无序序列细分至每组只剩一个元素
- 相邻两组按指定顺序归并，直到只剩一组即排序结束
算法实现
package com.zys.sort;
/**
* @program: dataStructure
* @description: 归并排序
* @author: Leo
* @create: 2019-08-01 16:46
**/
public class MergeSort {
/**
* 归并排序
*
* @param arr 待排序数组
* @param left 待排序左边部分开始索引
* @param right 待排序右边部分结束索引
*/
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
//对左边部分分解
mergeSort(arr, left, mid);
//对右边部分分解
mergeSort(arr, mid + 1, right);
//合并
merge(arr, left, mid, right);
}
}
/**
* 合并[left,mid] 与 [mid+1,right]两部分
*
* @param arr
* @param left
* @param mid
* @param right
*/
private static void merge(int[] arr, int left, int mid, int right) {
//l,r分别指向左边部分、右边部分开始索引
int l = left, r = mid + 1;
//临时数组
int[] temp = new int[right - left + 1];
//临时数组索引
int t = 0;
//1.遍历两部分，直到有一边全部遍历完
while (l <= mid && r <= right) {
//如果左边部分当前元素较小
if (arr[l] < arr[r]) {
//将arr[l]放入临时数组中
temp[t] = arr[l];
l++;
t++;
} else {
//将arr[r]放入临时数组中
temp[t] = arr[r];
r++;
t++;
}
}
//2.有一边遍历完，将另一边剩余元素全部放入临时数组中
while (l <= mid) {
temp[t] = arr[l];
l++;
t++;
}
while (r <= right) {
temp[t] = arr[r];
r++;
t++;
}
//3.将当前合并好的部分拷贝到原数组
t = 0;
l = left;
while (l <= right) {
arr[l] = temp[t];
l++;
t++;
}
}
}
快速排序
快速排序（Quick Sort）是对冒泡排序的一种改进。但是一种非稳定的排序算法，平均时间复杂度为O(nlogn)。
基本思想
从序列中挑选一个基准值，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比基准值要小，而另一部分逗比基准值大。然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
算法实现
package com.zys.sort;
/**
* @program: dataStructure
* @description: 快速排序
* @author: Leo
* @create: 2019-08-01 16:12
**/
public class QuickSort {
/**
* 快速排序
* @param arr 待排序数组
* @param left 待排序部分左索引
* @param right 待排序部分右索引
*/
public static void quickSort(int[] arr, int left, int right){
if (right < left)
return;
//储存基准值（取最左边的数）
int temp = arr[left];
int l = left, r = right;
while (l < r){
//从右向左找第一个比基准值小的数
while (arr[r] >= temp && r > l){
r--;
}
//从左向右找第一个比基准值大的数
while (arr[l] <= temp && l < r){
l++;
}
//如果 l 还在 r 的左边
if (l < r){
//交换下标 l、r 的值
int t = arr[l];
arr[l] = arr[r];
arr[r] = t;
}
}
//此时 l == r，交换基准值和 l(r) 对应的值
arr[left] = arr[l];
arr[l] = temp;
//对左边部分进行快速排序
quickSort(arr,left,l-1);
//对右边部分进行快速排序
quickSort(arr,l+1,right);
}
}
希尔排序
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
基本思想
希尔排序是把数据按下标的增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的数据越来越多，当增量减至1时，整个序列恰被分成一组，算法结束。
算法实现
package com.zys.sort;
/**
* @program: dataStructure
* @description: 希尔排序
* @author: Leo
* @create: 2019-07-31 21:41
**/
public class ShellSort {
/**
* 希尔排序（交换法） 不标准，且性能不好，基本不使用
*
* @param arr
*/
public static void shellSort(int[] arr) {
int temp = 0;
//gap为步长,每次缩小为上一次1/2
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
//遍历各组元素
for (int i = gap; i < arr.length; i++) {
for (int j = i - gap; j >= 0; j -= gap) {
//如果当前元素大于 同组后一个元素，交换
if (arr[j] > arr[j + gap]) {
temp = arr[j];
arr[j] = arr[j + gap];
arr[j + gap] = temp;
}
}
}
}
}
/**
* 希尔排序（移位法）
* @param arr
*/
public static void shellSort2(int[] arr) {
int curr = 0;
//进行分组，gap为步长,每次缩小为上一次1/2，第一次每组两个元素
for (int gap = arr.length / 2; gap > 0; gap /= 2){
//遍历各组元素，i = gap开始就跳过了每组的第一个元素，因为内部使用的是插入排序，所以认为第一个元素有序
for (int i = gap; i < arr.length; i++){
//暂存当前待插入的元素
curr = arr[i];
int j = i;
//将待插入元素和同组前一个元素比较（插入排序过程）
//注意：由于步长为gap，所以同组的前一个元素的索引为当前元素索引 - 步长（即 j 的同组的前一个元素的索引为 j - gap）
for (; j -gap >= 0 && curr < arr[j-gap]; j -= gap){
arr[j] = arr[j-gap];
}
//找到位置，插入
arr[j] = curr;
}
}
}
}
简单测试（JUnit）
package com.zys.test;
import com.zys.sort.*;
import org.junit.Before;
import org.junit.Test;
import java.util.Arrays;
/**
* @program: dataStructure
* @description: 排序测试类
* @author: Leo
* @create: 2019-05-23 20:42
**/
public class SortTest {
int[] arr;
@Before
public void generateUnSortedArray() {
arr = new int[]{5, 3, 7, 8, 1, 9, 4, 2, 6};
}
@Test
public void testCompare() {
//生成数组
generateRandomArray(80000);
//复制两份
int[] arr2 = new int[arr.length];
System.arraycopy(arr, 0, arr2, 0, arr.length);
int[] arr3 = new int[arr.length];
System.arraycopy(arr, 0, arr3, 0, arr.length);
long startTime = System.currentTimeMillis();
QuickSort.quickSort(arr, 0, arr.length - 1);
long endTime = System.currentTimeMillis();
System.out.println("快速排序花费时间：" + (endTime - startTime) + " ms");
startTime = System.currentTimeMillis();
MergeSort.mergeSort(arr2, 0, arr2.length - 1);
endTime = System.currentTimeMillis();
System.out.println("归并排序花费时间：" + (endTime - startTime) + " ms");
startTime = System.currentTimeMillis();
ShellSort.shellSort2(arr3);
endTime = System.currentTimeMillis();
System.out.println("希尔排序花费时间：" + (endTime - startTime) + " ms");
}
@Test
public void testShellSort() {
// printArray(arr);
// ShellSort.shellSort(arr);
// printArray(arr);
//生成数组
generateRandomArray(80000);
long startTime = System.currentTimeMillis();
ShellSort.shellSort2(arr);
long endTime = System.currentTimeMillis();
System.out.println("希尔排序花费时间：" + (endTime - startTime) + " ms");
}
@Test
public void testQuickSort() {
// printArray(arr);
// QuickSort.quickSort(arr,0,arr.length-1);
// printArray(arr);
//生成数组
generateRandomArray(8000000);
long startTime = System.currentTimeMillis();
QuickSort.quickSort(arr, 0, arr.length - 1);
long endTime = System.currentTimeMillis();
System.out.println("快速排序花费时间：" + (endTime - startTime) + " ms");
}
@Test
public void testMergeSort() {
// printArray(arr);
// MergeSort.mergeSort(arr, 0, arr.length - 1);
// printArray(arr);
//生成数组
generateRandomArray(8000000);
long startTime = System.currentTimeMillis();
MergeSort.mergeSort(arr, 0, arr.length - 1);
long endTime = System.currentTimeMillis();
System.out.println("归并排序花费时间：" + (endTime - startTime) + " ms");
}
/**
* 生成有n个元素的随机数组
*
* @param n 数组元素个数
*/
public void generateRandomArray(int n) {
arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = (int) (Math.random() * n * 10);
}
}
private void printArray(int[] a) {
for (int x : a) {
System.out.print(x + " ");
}
System.out.println();
}
}
