各种排序算法大合集
各种算法的比较：
快速排序：
希尔(Shell)排序：
要点
希尔(Shell)排序又称为缩小增量排序，它是一种插入排序。它是直接插入排序算法的一种威力加强版。
希尔排序的基本思想是：
把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。
随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。
我们来通过演示图，更深入的理解一下这个过程。
在上面这幅图中：
初始时，有一个大小为 10的无序序列。
在第一趟排序中，我们不妨设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。
接下来，按照直接插入排序的方法对每个组进行排序。
在第二趟排序中，我们把上次的 gap缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2的元素组成一组，可以分为 2 组。
按照直接插入排序的方法对每个组进行排序。
在第三趟排序中，再次把 gap缩小一半，即gap3 = gap2 / 2 = 1。这样相隔距离为 1 的元素组成一组，即只有一组。
按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。
需要注意一下的是，图中有两个相等数值的元素 5 和 5 。我们可以清楚的看到，在排序过程中，两个元素位置交换了。
所以，希尔排序是不稳定的算法。
朕的实现方法在此：
//测试类：
//注意：com.sxt.xxx 是包名
package org.sxt.test;
import java.util.Arrays;
import java.util.Scanner;
import com.sxt.b.BubbleSort;
import com.sxt.b.InsertSort;
import com.sxt.b.MergeSort;
import com.sxt.b.QuickSort;
import com.sxt.b.SelectSort;
import com.sxt.b.ShellSort;
import com.sxt.win.Show;
public class TestSort {
public static void main(String[] args) {
//1.给出无序数组
int arr[]= {72,6,57,88,60,42,83,73,48,85};
//2.输出无序数组
System.out.println("原数组："+Arrays.toString(arr));
while(true) {
//3.排序
Show.show();
Scanner sc = new Scanner(System.in);
int select = sc.nextInt();
switch(select)
{
case 1:QuickSort.quickSort(arr);break;
case 2:BubbleSort.bulleSort(arr);break;
case 3:SelectSort.select(arr);break;
case 4:InsertSort.insertSort(arr);break;
case 5:ShellSort.shellSort(arr);break;
case 6:MergeSort.merge_sort(arr);break;
}
//4.输出有序数列
System.out.println(Arrays.toString(arr));
}
}
}
package com.sxt.win;
public class Show {
public static void show() {
System.out.println("请选择排序方式：\n1.快速排序\n2.冒泡排序\n3.选择排序\n4.插入排序\n5.希尔遍历\n6.归并排序");
}
}
//冒泡排序
package com.sxt.b;
public class BubbleSort {
//冒泡排序算法
public static void bulleSort(int[] arr) {
for(int i=0;i<arr.length-1;i++)//扫描次数
{
for(int j=0;j<arr.length-1-i;j++) {
if(arr[j]>arr[j+1]) {
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
}
//插入排序
package com.sxt.b;
public class InsertSort {
public static void insertSort(int[] arr) {
/*遍历所有的数字看哪个比前面的小，
*如果小那就说明前面至少有一个比当前元素小的
*把当前元素塞到刚好比当前元素的小的元素前面，那么它后边的都要往后排一个
*/
for(int i=1;i<arr.length;i++) {
//如果当前数字比前一个数字小
if(arr[i]<arr[i-1]) {
//先把当前元素存起来
int temp=arr[i];
//遍历当前元素前面的元素
for(int j=i-1;j>0&&temp<arr[j];j--) {
//把前一个数字赋给后一个数字
arr[j+1]=temp;
}
}
}
}
}
//归并排序
package com.sxt.b;
public class MergeSort {
public static void merge_sort(int[] arr) {
mergesort(arr, 0, arr.length - 1);
}
public static void mergesort(int[] arr,int left, int right) {
if(left < right) return;
int middle = (left+right) / 2;
mergesort(arr, left, middle);
mergesort(arr, middle + 1, right);
mergeArr(arr, left, middle, right);//将左右两部分合并(左右两部分已经在递归中各自排好了序)
}
public static void mergeArr(int[] arr, int left, int middle, int right) {
int[] temp = new int[right - left + 1];//开辟新数组
int i = left, j = middle + 1, k = 0;
while(i <= middle && j <= right) {//经过这个循环后最多有一个数组有残余
temp[k++] = arr[i] < arr[j]? arr[i++] : arr[j++];
}
while(i <= middle) {//如果有残余加入到temp中
temp[k++] = arr[i++];
}
while(j <= right) {//如果有残余加入到temp中
temp[k++] = arr[j++];
}
// 将辅助数组数据写入原数组
int index = 0;
while(left <= right) {
arr[left++] = temp[index++];
}
}
}
//快速排序
package com.sxt.b;
public class QuickSort {
//分区函数
private static int partition(int[] arr,int low,int high) {
//1.指定左指针i和右针织j
int i=low;
int j=high;
//2.将第一个元素作为基准，挖坑带走
int x=arr[low];
//3.使用循环实现分区操作
while(i<j) {
//1.从右至左移动j，找到第一个小于基准值的元素，arr[j]，挖走
while(arr[j]>x&&i<j) {
j--;
}
//2.将arr[j]填入左边坑的位置，左指针i向右移动一个单位,指针右移一位i++
if(i<j) {
arr[i]=arr[j];
i++;
}
//3.从左向右移动i,找到第一个大于基准的元素arr[i]
while(arr[i]<x&&i<j) {
i++;
}
//4.将左侧找到的元素填入到右边的坑内,j--
if(i<j) {
arr[j]=arr[i];
j--;
}
}
//4.使用基准填坑，这是基准值的最终位置
arr[i]=x;
//5.返回基准的位置、
return i;
}
//快速排序算法
private static void quickSort(int[] arr,int low, int high) {//递归何时结束（low<high）,所剩元素大于两个
if(low<high) {
//分区操作，将一个数组分成两个分区，并返回分区索引
int index=partition(arr,low,high);
//将左分区进行快排
quickSort(arr,low,index-1);
//将右分区进行快排
quickSort(arr,index+1,high);
}
}
public static void quickSort(int[] arr) {
int low=0;
int high=arr.length-1;
quickSort(arr,low,high);
}
}
//选择排序
package com.sxt.b;
public class SelectSort {
public static void select(int[] arr) {
for(int i=0;i<arr.length-1;i++)
for(int j=i+1;j<arr.length;j++)
{
if(arr[i]>arr[j])
{
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
}
//希尔排序
package com.sxt.b;
import java.util.Arrays;
public class ShellSort {
public static void shellSort(int[] arr) {
int k=0;
//遍历所有的步长（步长每次减半）
for(int d=arr.length/2;d>0;d/=2)
{
//遍历所有组
for(int i=d;i<arr.length;i++) {
//遍历本组中的元素（相隔为d的元素是一组）
for(int j=i-d;j>=0;j-=d)
{
//如果当前元素大于加上步长后的元素则交换位置
if(arr[j]>arr[j+d]) {
int temp=arr[j];
arr[j]=arr[j+d];
arr[j+d]=temp;
}
}
}
k++;
System.out.println("第"+k+"次步长折半遍历"+Arrays.toString(arr));
}
}
}