笔试面试--总结7大常用排序算法（Java实现&详细）-白红宇

笔试面试--总结7大常用排序算法（Java实现&详细）

阅读量：4282 次

发布时间：2019-05-27

本文共 8630 字，大约阅读时间需要 28 分钟。

秋招了，总结整理一下常用的排序算法…

tip：文章略长，可直接跳到文末查看总结和巧记口诀。

package com.sap.stone;import java.util.Arrays;public class Sorting {
   		public static void main(String[] args) {
   		int [] array = {
   3,2,4,1,5,6,9,7,8};//		bubbleSort(array);//		insertSort(array);//		shellSort(array);//		selectSort(array);		heapSort(array);		System.out.println(Arrays.toString(array));	}	/**	 * 1.冒泡排序--【稳定】的排序算法	 * 最坏的情况是每次都需要交换，时间复杂度为O(n^2);最好的情况是内循环遍历一次后发现排序是对的, 然后退出循环, 时间复杂度为O(n).	 * 平均时间复杂度为O(n^2)	 * 只需要一个temp变量，所以空间复杂度为常量O(1)	 */	public static void bubbleSort(int [] array) {
   		if (array == null || array.length == 0) {
   			return;		}		int len = array.length;		//外层：需要len-1次循环比较		for (int i = 0; i < len-1; i++) {
   			//内层:每次循环需要两两比较，每次比较后，将当前较大的数放在最后			for (int j = 0; j < len-1-i; j++) {
   				if (array[j] > array[j+1]) {
   					swap(array, j, j+1);				}			}//end for		}//end for			}	/*	 * 交换数组i和j位置的数据	 */	public static void swap(int []array,int i,int j) {
   		int temp = array[i];		array[i] = array[j];		array[j] = temp;	}		/**	 * 3.直接插入排序 -- 【不稳定】	 * 思路：将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，则交换。	 * 	1.从第一个元素开始，这个元素可以认为已经被排序	 * 	2.取出一个元素，在已经排序的元素序列中【从后往前】扫描	 * 	3.如果这个元素（已排序）大于新元素，将这个元素后移一位。	 * 	4.找到已排序的元素小于或等于新元素的位置，插入新元素	 * 	 *  最好情况O(n),最坏情况和平均时间复杂度都是O(n^2),空间复杂度为常量O(1)	 */	public static void insertSort(int [] array) {
   		if (array == null || array.length == 0) {
   			return;		}		for (int i = 1; i < array.length; i++) {
   			int j = i-1;			int temp = array[i];  //先取出待插入的数保存，因为后移的过程中，会覆盖掉待插入的数			while (j >= 0 && array[j] > temp) {
    //如果比待插入的数大，就后移				array[j+1] = array[j];				j--;			} //end while			array[j+1] = temp;  //找到小于等于待插入数的位置，插入 待插入数据		} //end for	}		/**	 * 4.希尔排序：是简单插入排序的改进版,它与插入排序的不同之处在于，它会优先比较距离较远的元素，直接插入排序是稳定的；而希尔排序是【不稳定】的	 * 将整个待排序的序列分割成若干个子序列，分别对子序列进行直接插入排序；每次再将gap折半减小，循环上述操作；当gap=1时，利用直接插入，完成排序。	 * 思路：	 * 	1.选择一个增量序列t1,t2,……,tk,其中tk=1（一般初次取数组半长，之后每次减半，直到增量为1）	 * 	2.按增量序列个数k，对序列进行k趟排序	 * 	3.每趟排序，根据对应的增量ti，将待排序列分割成若干个长度为m的子序列，分别对各子序列进行直接插入排序。	 * 	 *  希尔排序的时间复杂度和步长的选择有关。最坏的时间复杂度为O(n^2)，当n在某个特定范围内，时间复杂度为O(n^1.3)	 */	//{3,2,4,1,5,6,9,7,8}	public static void shellSort(int [] array) {
   		int gap = array.length/2;   //初始增量为序列半长，之后每次减半;		for (; gap > 0; gap = gap/2) {
   			for (int j = 0; (j+gap) < array.length; j++) {
     //不断缩小gap，直到增量为1				for (int k = 0; (k+gap) < array.length; k+=gap) {
    //使用当前gap进行组内插入排序					//交换操作					if (array[k] > array[k+gap]) {
   						int temp = array[k];						array[k] = array[k+gap];						array[k+gap] = temp;						System.out.println(" Sorting: " + Arrays.toString(array));					} //end if				}//end for			}//end for		}//end for	}	/**	 * 5.选择排序	 * 	思想：在未排序序列中找到最小（大）元素，存放到未排序序列的起始位置；	 * 		1.从待排序列中，找到关键字最小的元素	 * 		2.如果最小元素不是待排序列的第一个元素，将其和第一个元素互换。	 * 		3.从剩下的n-1个元素中，找出关键字最小的元素，重复1,2步	 */	public static void selectSort(int [] array) {
   		for (int i = 0; i < array.length - 1; i++) {
     //一共进行n-1趟			int min = i;  //记录最小元素位置			for (int j = i+1; j < array.length; j++) {
    //选出待排序列中最小值的位置				if (array[j] < array[min]) {
   					min = j;  //更新最小元素位置				}			}//end for			if (min != i) {
   				swap(array, i, min);  //与第i个位置交换			}		}//end for	}	/**	 * 7.堆排序：【不稳定】	 * 大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]	 * 小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]	 * 思路：	 * 	1.将无序序列构建成堆，升序大顶堆（降序小顶堆）	 * 	2.将堆顶元素与末尾元素进行交换，使数组末尾元素最大。	 * 	3.然后继续调整堆，再将堆顶元素与当前末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。	 * 最好,最坏,平均时间复杂度都是O(nlogn),空间复杂度为O(1)	 */	public static void heapSort(int[] array) {
   		int length = array.length;		//build heap		for (int i = length/2; i >= 0; i--) {
   			adjustHeap(array, i, length-1);		}		//exchange, adjust heap		for (int i = array.length - 1; i > 0; i--) {
   			swap(array, 0, i);			adjustHeap(array, 0, i-1);		}	}	/**	 * 调整大顶堆（只是调整过程，建立在大顶堆已构建的基础上）	 * @param array	 * @param i	 * @param length	 */	private static void adjustHeap(int []array,int start,int end) {
   		int temp = array[start];		int child = start*2 + 1;		while (child <= end) {
   			if (child+1 <= end && array[child + 1] > array[child]) {
   				child++;			}			if (array[child] < temp) {
     //如果所有的孩子节点都小于父节点，就结束循环				break;			}else {
   				array[start] = array[child];				start = child; //迭代				child = child*2 + 1;			}		} //end while		array[start] = temp;	}}

2.快排，是冒泡的一个改进；

注意：快排【不稳定】，它有可能打破原来值为相同的元素之间的顺序。

快拍思路：

采用分治法，通过一趟排序将数据分为两部分，比哨兵小的元素放在哨兵的前面，比哨兵大的元素放在哨兵后面；

递归子序列

最好情况和平均时间复杂度都是【O(nlogn)】；最坏时间复杂度为O(n^2),空间复杂度为O(1).

import java.util.Arrays;public class QuickSort {
   		public static void main(String[] args) {
   		int [] array = {
   1,2,9,7,6,5,8,4,3};		int [] array2 = {
   1,2,9,7,6,5,8,4,3};		quickSort(array, 0, array.length-1);		System.out.println(Arrays.toString(array));		System.out.println("======================");		quickSort_partition(array2, 0, array.length-1);		System.out.println(Arrays.toString(array2));	}		//方式1: partition版本	public static void quickSort_partition(int [] array,int start, int end) {
   		if (start >= end) {
   			return;		}		int index = patition(array, start, end);		quickSort_partition(array, start, index-1);		quickSort_partition(array, index+1, end);	}	public static int patition(int[] array,int start,int end) {
   		int flag = array[start]; //哨兵		while (start < end)		{
   			while(start < end && array[end] >= flag )  //从后往前 				end--;			swap(array,start, end);  //遇到比哨兵小的，就交换			while (start < end && array[start] <= flag)   //从前往后				start++;			swap(array, start, end); //遇到比哨兵大的，就交换		}		return start;	}	//交换	public static void swap(int[] array,int i,int j) {
   		int temp = array[i];		array[i] = array[j];		array[j] = temp;	}	//方式2: 挖坑版本	public static void quickSort(int[] array,int low,int high) {
   		if (array == null || array.length <= 0) {
   			return;		}		if (low >= high) {
   			return;		}		int left = low;		int right = high;		int key = array[left];  //挖坑1:保存哨兵		while (left < right) {
   			while (left < right && array[right] >= key) {
   				right--;			}			array[left] = array[right]; //挖坑2:从后向前找到比哨兵小的元素，插入到哨兵位置坑1中			while(left < right && array[left] <= key) {
   				left++;			}			array[right] = array[left]; //挖坑3:从前往后找到比哨兵大的元素，放到刚才挖的坑2中		}//end while		array[left] = key;  //哨兵值填补到坑3中，准备分治递归快排				System.out.println("Sorting: " + Arrays.toString(array));		quickSort(array, low, left-1);  //递归		quickSort(array, left+1, high);	}}

6.归并排序&利用归并排序统计数组中的逆序对

归并排序:是将两个(或两个以上)有序表合并成一个新的有序表，即把待排序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列.

归并排序：【稳定】；

平均时间复杂度,最好,最坏时间复杂度都是【O(nlogn)】，空间复杂度为O(n).

实现思路：(采用递归)

* 1.将序列每相邻的两位数字进行归并操作，形成n/2个子序列，排序后每个子序列包含两个数字

* 2.将上述序列再次归并，形成 n/4个序列，每个序列包含四个元素；

* 3.重复step2，直到所有元素排列完。

import java.util.Arrays;public class MergeSort {
   	public static void main(String[] args) {
   		int[] array = {
   3,2,1,4,5,9,7,8,6};		MergeSort mergeSort = new MergeSort();		int inversePairsCount = mergeSort.InversePairs(array);		System.out.println("inversePairs = " + inversePairsCount);		System.out.println(Arrays.toString(array)); 	}	/**	 * 统计数组中的逆序对	 * @param array	 */	int count;	public int InversePairs(int[] array) {
   		count = 0;		if (array != null && array.length != 0) {
   			mergeSortUp2Down(array, 0, array.length - 1);		}		return count;	}	//归并排序，从上到下	public void mergeSortUp2Down(int[] array,int start,int end) {
   		//递归出口		if (start >= end) {
   			return;		}		int mid = (start + end) >> 1;		//将数据分成左右两个数组		//递归分到每个数组只有一个元素		mergeSortUp2Down(array,start,mid);		mergeSortUp2Down(array,mid+1,end);				merge(array,start,mid,end);	}	//将一个数组中的两个相邻的【有序区间】合并成一个	public void merge(int[] array, int start,int mid,int end) {
   		int[] temp = new int[end - start + 1]; // 申请额外空间保存归并之后数据				int i = start,j = mid+1, k = 0;		//取两个序列中的较小值放入新数组		while (i <= mid && j <= end) {
   			if (array[i] <= array[j]) {
   				temp[k++] = array[i++];			}else {
    //如果前面的数大于后面的数，就构成逆序对				temp[k++] = array[j++];				//合并时，出现前面的数组值array[i]大于后面数组值array[j]时；则前面数组array[i]~array[mid]都是大于array[j]的，				//因为array[start]-array[mid]以及array[mid+1]-array[end]都已经是有序区间,所以count += mid-i+1.				count = (count + mid - i + 1)%1000000007;  //统计数组中逆序对的个数			}		}		//序列a中多余的元素移入新数组		while (i <= mid) {
   			temp[k++] = array[i++];		}		//序列b中多余的元素移入新数组		while (j <= end) {
   			temp[k++] = array[j++];		}		//覆盖原数组		for (k = 0; k < temp.length; k++)            array[start + k] = temp[k];	}}

总结如下：