一、排序概述

?排序（又称分类、整序）是指将无序序列排成一个有序序列（由小到大或由大到小）的运算。用于作为排序依据的数据项称为关键词，也就说排序算法是基于关键词从小到大或从大到小进行排序的。本文中，对以下7种常用的内部排序算法进行使用：冒泡排序、直接插入排序、简单选择排序、希尔排序、堆排序、归并排序、快速排序。并通过获取每种排序算法的运行时间以获得不同排序算法所需时间上的直观感受。

二、排序算法实现

1.简单选择排序

a.实现原理

第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置。然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。

b.代码：

//简单选择排序
	private static void selectSort(int[] arr) {
		for (int i = 0; i < arr.length; i++) {//从第一个数开始
			for (int j = i + 1; j < arr.length; j++) {//与当前数后面的所有数进行比较，将最小的数放在下标为i的位置上
				if(arr[i] > arr[j]) {
					int temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
			}
		}		
	}

2.冒泡排序

a.实现原理

对于一组要排序的元素列，依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面，如此继续，直到比较到最后的两个数，将小数放在前面，大数放在后面，重复步骤，直至全部排序完成。

b.代码：

//冒泡排序
	private static void bubblingSort(int[] arr) {

		for (int i = 0; i < arr.length - 1; i++) {
			for (int j = arr.length - 1; j > i; j--) {
				if(arr[j] < arr[i]) {
					int temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
				
			}
		}
	}

?3.直接插入排序

a.实现原理

依次将数组中一个数插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。

b.代码:

//直接插入排序
	private static void insertSort(int[] arr) {

		//第一个记录本身就是有序的，所以从第二个元素开始
        for(int i=1;i<arr.length;i++){
            int temp=arr[i];//使用临时变量存储待插入的值
            int j=i-1;
            while(j>=0&&arr[j]>temp){
                arr[j+1]=arr[j];//当前面的数比待插入的数要大时则逐个后移
                j--;
            }
            //当找到第一个小于待插入的数字时，需要将待插入数字插入到它的后一个位置上,故为j+1
            arr[j+1]=temp;
        }
	}

4.希尔排序

a.实现原理

希尔排序是把序列按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量的逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个序列恰好被分为一组，算法便结束。

b.代码:

//希尔排序
	private static void shellSort(int[] arr) {
		 //间隔序列，在希尔排序中我们称之为增量序列
	    for(int group = arr.length/2;group > 0;group /= 2){
	        //插入排序
	        //从group开始，按照顺序将每个元素依次向前插入自己所在的组
	        for(int i = group;i < arr.length;i++){
	            //cur站起来，开始找位置
	            int cur=arr[i];
	            //该组前一个数字的索引
	            int j = i - group;
	            while(j >=0 && arr[j] >= cur){
	                arr[j + group] = arr[j];
	                j-=group;
	            }
	            //cur插入找到了自己的位置，坐下
	            arr[j + group] = cur;
	        }
	    }	
	}

5.堆排序

a.实现原理

利用堆这种数据结构所设计的一种排序算法。大顶堆的根节点是二叉树中最大的节点，每次操作提取此最大节点，完成排序。

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；

小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

b.代码:

//堆排序
	private static void heapSort(int[] arr) {
		//从倒数第一个非叶子节点开始
		for (int i = arr.length / 2 - 1; i >= 0; i--){
			//从第一天非叶子节点从下至上，从左至右调整结构
			adjustHeap(arr,i, arr.length);
		}

		//将堆顶元素与末尾元素交换 将最大元素沉到数组末尾 + 重新调整堆结构
		for (int i = arr.length - 1; i > 0 ; i--){
			//交换堆顶元素和末尾元素
			int temp = arr[i];
			arr[i] = arr[0];
			arr[0] = temp;
			//交换后的末尾元素忽略(j--) 不再参与堆结构的调整
			//重新调整堆结构
			adjustHeap(arr,0,i);
		}    
	}

	private static void adjustHeap(int[] arr, int index, int length) {
		//取出当前元素
		int temp = arr[index];
		//i节点是index节点的左子节点
		for (int i = 2 * index + 1; i < length; i = 2 * i + 1) {
			//表明左子节点小于右子节点
			if (i+1 < length && arr[i] < arr[i+1]){            
				i++;//将指针移至较大节点
			}

			if (arr[i] > temp){ //如果子节点大于父节点   
				arr[index] = arr[i];//将较大值赋给当前节点
				index = i; //指针移向子节点
			}else{
				break;
			}
		}
		//循环结束，已经将最大值放在了堆顶    
		arr[index] = temp;//将temp值放到最终的位置		
	}

6.归并排序

a.实现原理

归并排序是建立在归并的有效操作上进行排序，主要采用分治法将已有序的子序列合并，得到完全有序的序列。即先让每一小段有序，再让小段之间变得有序。

将两个有序段归并为一个有序段，称为二路归并；有序段称为归并段。

b.代码

//归并排序
	private static void mergeSort(int[] arr, int left, int right, int[] temp) {
		if (left == right){//当拆分到数组当中只要一个值的时候，结束递归
			return;
		}
		int mid = (left+right) / 2;//找到下次要拆分的中间值
		mergeSort(arr,left,mid,temp);//记录树左边的
		mergeSort(arr,mid + 1,right,temp);//记录树右边的

		//合并两个区间
		for (int i = left; i <= right; i++) {
			temp[i] = arr[i]; //temp就是辅助列表，新列表的需要排序的值就是从辅助列表中拿到的
		}
		int i = left;//给辅助数组里面的值标点
		int j = mid +1;
		for (int k = left; k <= right ; k++) {//k 就为当前要插入的位置
			if (i == mid + 1){
				arr[k] = temp[j];
				j++;
			}else if (j == right+1){
				arr[k] = temp[i];
				i++;
			}
			else if (temp[i] <= temp[j]){
				arr[k] = temp[i];
				i++;
			}else {
				arr[k] = temp[j];
				j++;
			}
		}
	}

7.快速排序

a.实现原理

在待排序的n个元素中任取一个元素(通常取第一个元素)作为基准，把该元素放入最终位置后，整个数据序列被基准分割成两个子序列，所有小于基准的元素放置在前子序列中，所有大于基准的元素放置在后子序列中，并把基准排在这两个子序列的中间，这个过程称为划分，然后对两个子序列分别重复操作，直到每个子序列中只有一个元素或为空为止。

b.代码:

//快速排序
	private static void fastSort(int[] arr, int left, int right) {
		
        if(left > right){
            return;
        }
        int i = left;
        int j = right;  
        int temp = arr[left];//序列的第一个记录作为基准
        while (i < j) {
            //先看右边，依次往左递减
            while (temp <= arr[j] && i < j) {
                j--;
            }
            //再看左边，依次往右递增
            while (temp >= arr[i] &&i < j) {
                i++;
            }
            //如果满足条件则交换
            if (i<j) {
                int t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }
        }
        //最后将基准为与i和j相等位置的数字交换
         arr[left] = arr[i];
         arr[i] = temp;
        //递归调用左半数组
         fastSort(arr, left, j - 1);
        //递归调用右半数组
         fastSort(arr, j + 1, right);
		
	}

8.主方法与其他方法

a.主方法代码:

public static void main(String[] args) {
		int n = 30000;//数组大小
		int[] a = new int[n];//定义动态数组
		for (int i = 0; i < n; i++) {//为数组随机赋值
	        a[i] = (int) (Math.random()*10000);
	    }
		mean(a);//菜单方法	
	}

b.菜单(即对排序算法进行选择使用)代码:

//菜单
	private static void mean(int[] a) {
		Scanner input = new Scanner(System.in);
		while(true) {
			System.out.println("----------------------这是分界线----------------------");
			System.out.println("1.简单选择排序\n2.冒泡排序\n3.直接插入排序\n4.希尔排序\n5.堆排序\n6.归并排序\n7.快速排序");
			System.out.print("请选择排序方式:");
			int choice = input.nextInt();
			int[] arr = Arrays.copyOf(a,a.length);//复制一个数组
			System.out.println("排序前前二十个数字:" + dis(arr));
			switch (choice) {
			case 1: {
				long t1 = PrintSystemTime();
				selectSort(arr);//简单排序
				long t2 = PrintSystemTime();
				System.out.println("简单选择排序后前二十个数字:" +  dis(arr));
				System.out.println("排序所花时间为:" + (t2 - t1) + "毫秒");
				break;
				}
			case 2: {
				long t1 = PrintSystemTime();
				bubblingSort(arr);//冒泡排序
				long t2 = PrintSystemTime();
				System.out.println("冒泡排序后前二十个数字:" +  dis(arr));
				System.out.println("排序所花时间为:" + (t2 - t1) + "毫秒");
				break;
				}
			case 3: {
				long t1 = PrintSystemTime();
				insertSort(arr);//直接插入排序
				long t2 = PrintSystemTime();
				System.out.println("直接插入排序后前二十个数字:" +  dis(arr));
				System.out.println("排序所花时间为:" + (t2 - t1) + "毫秒");
				break;
				}
			case 4: {
				long t1 = PrintSystemTime();
				shellSort(arr);//希尔排序
				long t2 = PrintSystemTime();
				System.out.println("希尔排序后前二十个数字:" +  dis(arr));
				System.out.println("排序所花时间为:" + (t2 - t1) + "毫秒");
				break;
				}
			case 5: {
				long t1 = PrintSystemTime();
				heapSort(arr);//堆排序
				long t2 = PrintSystemTime();
				System.out.println("堆排序后前二十个数字:" +  dis(arr));
				System.out.println("排序所花时间为:" + (t2 - t1) + "毫秒");			
				break;
				}
			case 6: {
				long t1 = PrintSystemTime();
				mergeSort(arr,0,arr.length - 1,new int[arr.length]);//归并排序
				long t2 = PrintSystemTime();			
				System.out.println("归并排序后前二十个数字:" +  dis(arr));
				System.out.println("排序所花时间为:" + (t2 - t1) + "毫秒");
				break;
				}
			case 7:	{
				long t1 = PrintSystemTime();
				fastSort(arr,0,arr.length - 1);//快速排序
				long t2 = PrintSystemTime();
				System.out.println("快速排序后前二十个数字:" +  dis(arr));
				System.out.println("排序所花时间为:" + (t2 - t1) + "毫秒");		
				break;
				}
			case 0:break;
			default:
				System.out.println("输入错误！请重新输入！");break;
			}	
			System.out.print("按任意键继续，按n退出:");
			String str = input.next();
			if(str.equals("n")) {
				System.out.println("已退出！");
				return; 
			}
			if(choice == 0) {
				System.out.println("已退出！");
				return;
			}
		}
	}

c.数组输出和返回系统当前时间戳代码:

//获取系统当前时间戳
	private static long PrintSystemTime(){
        Calendar c = Calendar.getInstance();
        long time = c.getTimeInMillis();
        //long second = c.get(Calendar.SECOND);
//        System.out.println("\n"+c.getTimeInMillis());
        return time;
    }
	
	//输出数组
	private static String dis(int[] arr) {
//		复制数组前20个
		int[] dis = Arrays.copyOfRange(arr,0,20);
		return Arrays.toString(dis);
	}