各种排序算法大合集_数据结构排序合集

各种算法的比较：

快速排序：

希尔(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));
	  }
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

package com.sxt.win;


public class Show {
	public static void show() {
		System.out.println("请选择排序方式：\n1.快速排序\n2.冒泡排序\n3.选择排序\n4.插入排序\n5.希尔遍历\n6.归并排序");
	}
}
1
2
3
4
5
6
7
8

//冒泡排序
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;
				}
			}
		}
		
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

//插入排序
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;
				}
			}
		}
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

//归并排序
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++];
		  }
		}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

//快速排序
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);
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

//选择排序
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;
				}
			}
	}
    
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

//希尔排序
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));
		}
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31