Java数据结构与算法之常见排序算法总结

目录：
1.概述
2.常用排序方法总结
3.冒泡排序
4.选择排序
5.插入排序
6.归并排序
7.快速排序
8.shell排序

1.概述
学过排序算法的朋友可能都知道排序算法有很多种，那在实际应用中我们应该选择哪一种比较恰当呢？当然我们排序算法各有优势
的，在选择的时候也需要我们去衡量，而他的衡量标准就是看该算法的时间复杂度和空间复杂度，所谓的时间复杂度和空间复杂度本质就是
考虑算法在时间效率和内存上的优劣。

2.常用排序方法总结

3.冒泡排序
(1)思路：冒泡排序的思路就是在未排序的序列中从一开始对相邻的两个数依次对比小数往前冒泡，大数向后沉，第一轮结束后最后一个数
的位置已经固定，所以仅仅对前面n-1的数进行第二轮排序，依此类推，最终得到的序列则为有序序列。

(2)Java代码实现：

package com.arithmetic.test;


public class BubbleSort {
	/*
	 * 无参构造方法
	 */
	public BubbleSort() {
	}
	/*
	 * 冒泡排序法
	 */
	public int[] bubbleSort(int[] array){
		int temp;
		for (int i = 1; i <= array.length; i++) {
			for (int j = 0; j < array.length-i; j++) {
				if (array[j]>array[j+1]) {
					temp = array[j+1];
					array[j+1] = array[j];
					array[j] = temp;
				}
			}
		}
		return array;
	}
	
	public static void main(String[] args) {
		int[] arr ={12,34,56,778,999,445,33,900,34,223,24,567,788,77};
		System.out.print("排序前:");
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+"  ");
		}
		System.out.println();
		arr = new BubbleSort().bubbleSort(arr);
		System.out.print("排序后:");
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+"  ");
		}
	}
	
}

4.选择排序
(1)思路：在乱序数组中假设第一个数位最小，然后依次让后面的数与之对比，一旦有比他小的数就交换他们的位置，一趟下来第一个数就是序列中
最小的一个元素了，然后从第二个元素开始重复上面的操作，最终的到就是有序序列了。


(2)Java代码实现：

package com.arithmetic.test;


public class SelectSort {


	public SelectSort() {}
	/*
	 * 选择排序方法
	 */
	public int[] selectSort(int [] arr){
		int minIndex;
		int temp;
		for (int i = 0; i < arr.length-1; i++) {
			minIndex = i;
			for (int j = i+1; j < arr.length; j++) {
				if (arr[minIndex]>arr[j]) {
					temp = arr[j];
					arr[j] = arr[minIndex];
					arr[minIndex]=temp;
				}
			}
		}
		return arr;
	}
	
	public static void main(String[] args){
		int[] arr ={1,34,56,778,999,445,33,900,34,223,24,567,788,77};
		System.out.print("排序前:");
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+"  ");
		}
		System.out.println();
		arr = new SelectSort().selectSort(arr);
		System.out.print("排序后:");
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+"  ");
		}
	}
}

5.插入排序
(1)思路:插入排序的规则就像玩扑克摸牌，每摸一张牌对比一次手上的牌，如果比手上的都大就放到最后面，比手上都小就放到最前面
如果在中间就把比他大的往后移，然后把它插进去，摸完牌后手上的的牌就是有序的了。

(2)Java代码实现：

 

package com.arithmetic.test;


public class InsertSort {


	public InsertSort() {
	}


	/*
	 * 插入排序
	 * 
	 */
	public int[] insertSort(int[] arr){
		
		for (int i = 1; i < arr.length; i++) {
			//value为当前要插入的值
			int value = arr[i];
			int j=i-1;
			//在当前值之前已经排列好的数组中依次对比，如果值都比当前值大，则将当前值后移一位，直到比当前值小或者没有数值为止
			while (j>=0&&arr[j]>value) {
				arr[j+1] = arr[j];
				j--;
			}
			//将当前要插入的值插入
			arr[j+1] = value;
		}
		return arr;
	}
	
	public static void main(String[] args) {
		int[] arr ={1,34,56,778,999,445,33,900,34,223,24,567,788,77};
		System.out.print("排序前:");
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+"  ");
		}
		System.out.println();
		arr = new InsertSort().insertSort(arr);
		System.out.print("排序后:");
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+"  ");
		}
	}


}

 

6.归并排序
(1)思路：归并排序就是通过递归的方式将待排序列分成若干个序列，保证每个子序列是有序的，然后再将这些有序的子序列合并
成一个完整的有序序列。


(2)Java代码实现：

package com.arithmetic.test;


public class MergeSort {


	public MergeSort() {}
	/*
	 * 归并排序方法
	 */
/*	public void Sort(int[] arr){
		mergeSort(arr, 0, arr.length-1);
	}*/
	public void mergeSort(int[] arr,int low,int height){
		if (low 

7.快速排序

(1)思路:找一个基准值(一半设置为序列第一个),然后让序列元素依次与之对比，将比他小的值放到他左边(前面),将比他大的值放到

他右边(后面),然后再取新序列的第一个元素继续如上操作，依次递归得到最后的有序序列。



(2)Java代码实现：
package com.arithmetic.test;


public class QuickSort {


	public QuickSort() {}
	
	public int[] quickSort(int[] arr,int low,int height){
		//判斷初始的低位是否比高位低
		if (low=base) {
					height--;
				}
				//將高位值放到低位也就是左邊
				if (low 

8.shell排序

(1)思路:初始化一个步长step（一般为长度的一半），然后对相隔长度为step的数组成的若干数组进行插入排序，然后将初始的step

折半，再进行相同的操作,直到step<1为止。



(2)Java实现代码：
package com.arithmetic.test;


public class ShellSort {


	public ShellSort() {}
	/*
	 * 希尔排序方法
	 */
	public void shellSort(int[] arr){
		int step = arr.length/2;
		while (step>=1) {
			for (int i = step; i < arr.length; i++) {
				//需要插入的值
				int value = arr[i];
				//前一个插入值的索引下标
				int j =i-step;
				//如果存在前一个值，并且大于需要插入的值
				while (j>=0&&arr[j]>value) {
					//就将前一个插入的值后移一位
					arr[j+step]=arr[j];
					//循环对比判断插入当前值之前插入值得大小，并作出相应的处理
					j-=step;
				}
			
				//arr[i]=value;
				//这里不能用arr[i]=value虽然从一开始j =i-step看起来j+step=i，但是后面在内层循环中j是在变化的，而i没变
				arr[j+step] = value;
			}
			//步长缩小半
			step=step/2;
		}
	}


	public static void main(String[] args) {
		int[] arr ={1,34,56,778,999,445,33,900,34,223,24,567,788,77};
		System.out.print("排序前:");
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+"  ");
		}
		System.out.println();
		new ShellSort().shellSort(arr);
		System.out.print("排序后:");
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+"  ");
		}
	}


}


ps：排序算法就先总结一点常见的算法类型，其他的后面时间比较充足的时候再学习