经典排序算法归纳

算法概述

算法分类

十种常见排序算法可以分为两大类：

• 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
• 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

算法复杂度

相关概念

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
• 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

冒泡排序（Bubble Sort）

动图演示

Java实现

/** * 冒泡排序 平均时间复杂度为o(n2)，最好复杂度为o(n)，空间复杂度为o(1) *  * @author monkJay */public class BubbleSort {	public static void solution(int[] array) {		int len = array.length;		// 从第一个开始直到倒数第二个		for (int i = 0; i < len - 1; ++i) {			// 每比较一轮，都会有一个已排序好的数字，i就是已经排序好了的个数			for (int j = 1; j < len - i; ++j) {				// 如果后面的数字小于前面的数字，则交换				if (array[j] < array[j - 1]) {					int tmp = array[j];					array[j] = array[j - 1];					array[j - 1] = tmp;				}			}		}	}	public static void main(String[] args) {		int[] array = new int[] { 2, 1, 4, 3, 6, 5, 9, 8 };		solution(array);		for (int i = 0; i < array.length; ++i) {			System.out.print(array[i] + " ");		}	}}

选择排序（Selection Sort）

动图演示

Java实现

/** * 选择排序(最稳定的排序算法，不算什么序列时间复杂度都是o(n2)) 每次从未排序的序列中选择一个最小(大)的数放在已排序的序列的后面 * 平均时间复杂度为o(n2)，最好复杂度为o(n2)，空间复杂度为o(1) *  * @author monkJay */public class SelectionSort {	public static void solution(int[] array) {		int len = array.length;		for (int i = 0; i < len - 1; ++i) {			int minIndex = i;			for (int j = i + 1; j < len; ++j) {				if (array[minIndex] > array[j]) {					minIndex = j;				}			}			int tmp = array[minIndex];			array[minIndex] = array[i];			array[i] = tmp;		}	}}

插入排序（Insertion Sort）

动图演示

Java实现

/** * 插入排序 | 选择未排序序列的第一个数，插入到已排序序列中合适得位置(从后往前找，直到找到一个比当前数小或者等于的数，插在它后面) * 平均时间复杂度为o(n2)，最好复杂度为o(n)，空间复杂度为o(1) *  * @author monkJay */public class InsertionSort {	public static void solution(int[] array) {		int len = array.length;		for (int i = 1; i < len; ++i) {			int preIndex = i - 1;			int current = array[i];			while (preIndex >= 0 && array[preIndex] > current) {				// 如果有序序列中的数大于要插入的数，则后移一个位置(将自己的位置空出来)				array[preIndex + 1] = array[preIndex];				// 继续往前寻找				--preIndex;			}			// 找到了适合的位置(终于找到一个小于等于要插入的数了)，将数字插在这个位置后面			array[preIndex + 1] = current;		}	}}

希尔排序（Shell Sort）

动图演示

Java实现

/** * 希尔排序 将一个序列在逻辑上根据指定的步长分组，对每个分组进行插入排序(插入排序时的移动是根据当前步长移动查找的) *  * @author monkJay */public class ShellSort {	public static void solution(int[] array) {		int len = array.length;		// 步长从当前长度的一半开始，每一轮将步长减为一半，直到最后小于1结束		for (int gap = len / 2; gap > 0; gap /= 2) {			// 取值从步长开始，这里其实就是将直接插入排序中的1全部换成了步长gap			// 其它和直接插入排序一样			for (int i = gap; i < len; ++i) {				int preIndex = i - gap;				int current = array[i];				while (preIndex >= 0 && array[preIndex] > current) {					array[preIndex + gap] = array[preIndex];					preIndex = preIndex - gap;				}				array[preIndex + gap] = current;			}		}	}}

归并排序（Merge Sort）

动图演示

Java实现

/** * 二路归并排序 用到了分治的思想，不断往下细分，分到只有一个数字(认为是有序的)的时候开始合并，最后合并为一个有序的数组 *  * @author monkJay */public class MergeSort {	public static void solution(int[] array) {		int len = array.length;		if (len == 0) {			return;		}		int left = 0;		int right = len - 1;		int[] tmp = new int[len];		mergeSort(array, tmp, left, right);	}	public static void mergeSort(int[] array, int[] tmp, int left, int right) {		// 如果还可以分组，其实最后是分到只有一个数(认为一个数是有序的)		if (left < right) {			int center = left + (right - left) / 2;			// 左边的数组继续往下分			mergeSort(array, tmp, left, center);			// 右边的数组继续往下分			mergeSort(array, tmp, center + 1, right);			// 将左右两个有序的数组合并			merge(array, tmp, left, center, right);		}	}	public static void merge(int[] array, int[] tmp, int left, int center,			int right) {		int i = left, j = center + 1;		// 将要合并的两个有序数组，从小到大有序的放在辅助数组中		for (int k = left; k <= right; ++k) {			// 如果左边的数组遍历完了，就直接放右边的数组			if (i > center) {				tmp[k] = array[j++];			}			// 如果右边的数组遍历完了，就直接放左边的数组			else if (j > right) {				tmp[k] = array[i++];			}			// 将小的放在辅助数组中			else if (array[i] <= array[j]) {				tmp[k] = array[i++];			} else {				tmp[k] = array[j++];			}		}		// 将辅助数组中的值复制到原数组中		for (int k = left; k <= right; ++k) {			array[k] = tmp[k];		}	}}

快速排序（Quick Sort）

动图演示

Java实现

/** * 快速排序 * 通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小， * 则可分别对这两部分记录继续进行排序，以达到整个序列有序。 * @author monkJay */public class QuickSort {	public static void solution(int[] array) {		int len = array.length;		if (len == 0) {			return;		}		int left = 0, right = len - 1;		quickSort(array, left, right);	}	public static void quickSort(int[] array, int left, int right) {		if (left < right) {			int partitionIndex = partition(array, left, right);			quickSort(array, left, partitionIndex - 1);			quickSort(array, partitionIndex + 1, right);		}	}    // 第一种分区方法	public static int partition(int[] array, int left, int right) {        // 选取左边第一个数作为中轴数		int pivot = left;        // 从中轴数后面一个位置开始比较		int index = pivot + 1;        // 保证指针左边的数都是小于中轴数的		for (int i = left + 1; i <= right; i++) {            // 如果小于中轴数，将当前数的位置和中轴指针交换			if (array[i] < array[pivot]) {				swap(array, i, index);                // 指针继续后移				++index;			}		}        // 将中轴数的位置和指针左边一个位置交换，也就是把中轴数换到中间		swap(array, pivot, index - 1);        // 最后返回这个中轴数的位置		return index - 1;	}    // 第二种分区方法	// public static int partition(int[] array, int left, int right) {	// int i = left, j = right + 1;	// int pivot = array[left];	// while (i < j) {	//	// while (array[--j] > pivot && i < j)	// ;	// while (array[++i] < pivot && i < j)	// ;	// if (i < j) {	// swap(array, i, j);	// }	// }	// swap(array, left, j);	// return j;	// }	public static void swap(int[] array, int a, int b) {		int tmp = array[a];		array[a] = array[b];		array[b] = tmp;	}}

堆排序（Heap Sort）

动图演示

Java实现

/** * 堆排序 先构建一个最大(小)堆，每次都堆顶取一个数，并把最后一个数交换到堆顶，然后重新调整堆，重复，直到堆中最后一个数 * 最大堆得到从小到大的排序，最小堆得到从大到小的排序 *  * @author HP * */public class HeapSort {	public static void solution(int[] array) {		int len = array.length;		if (len == 0) {			return;		}		buildHeap(array);		heapSort(array);	}	/**	 * 下沉调整 用于堆的删除，还可用于构建二叉堆	 * 	 * @param array 存放堆的数组	 * @param parentIndex 父结点位置	 * @param len 数组长度	 */	public static void downAdjust(int[] array, int parentIndex, int len) {		// 先计算得到左孩子		int childIndex = parentIndex * 2 + 1;		// 保存父结点的值		int tmp = array[parentIndex];		while (childIndex < len) {			// 如果右孩子存在，且右孩子的值比左孩子要小，则将孩子节点定位到右孩子			if (childIndex + 1 < len					&& array[childIndex + 1] < array[childIndex]) {				childIndex++;			}			// 如果父结点的值比两个孩子都小，不用调整了，直接结束			if (tmp < array[childIndex]) {				break;			}			// 将孩子节点的值赋给父结点，继续下沉			array[parentIndex] = array[childIndex];			// 将孩子节点作为新的父结点			parentIndex = childIndex;			// 重新计算左孩子的位置			childIndex = parentIndex * 2 + 1;		}		// 节点调整结束，将最初需要调整的那个节点赋值到最终位置		array[parentIndex] = tmp;	}	/**	 * 其实就是让每个非叶子节点依次下沉	 * 构造堆 时间复杂度是线性的	 * @param array 要构造堆的数组	 */	public static void buildHeap(int[] array) {		int len = array.length;		// 找到最后一个节点的父结点		int startIndex = (len - 2) / 2;		for (int i = startIndex; i >= 0; --i) {			downAdjust(array, i, len);		}	}	/**	 * 堆排序 每次都堆顶取一个数，并把最后一个数交换到堆顶，然后重新调整堆，重复，直到堆中最后一个数	 * @param array 	 */	public static void heapSort(int[] array) {		for (int i = array.length - 1; i > 0; --i) {			int tmp = array[0];			array[0] = array[i];			array[i] = tmp;			// 从堆顶开始调整			downAdjust(array, 0, i);		}	}}

计数排序（Counting Sort）

动图演示

Java实现

/** * 计数排序 * 计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 * 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。 * @author HP */public class CountingSort {	public static void solution(int[] array) {		int len = array.length;		if (len == 0) {			return;		}		int maxValue = 0;        // 得到最大值		for (int i = 0; i < len; ++i) {			if (array[i] > maxValue) {				maxValue = array[i];			}		}		int[] bucket = new int[maxValue + 1];		// 将桶用0填充		Arrays.fill(bucket, 0);		// 记录每个元素出现的个数		for (int i = 0; i < len; ++i) {			bucket[array[i]]++;		}		int index = 0;		for (int i = 0; i < bucket.length; ++i) {            // 将桶中的元素往原数组放			while (bucket[i] > 0) {				array[index++] = i;				bucket[i]--;			}		}	}}

topK的四种解法

构造大顶堆

算法分析：用数组前k个数构造一个大顶堆，然后依次比较后面的数，如果小于堆顶，则换掉，重新调整堆，最后的堆顶元素就是第k大的元素。时间复杂度为O(klogk)。Java实现

public class TopK {	public static int topK_Solution(int[] input, int k) {		int len = input.length;		if (len == 0 || k <= 0 || k > len) {			return 0;		}        // 先把前k个数构造成一个堆		int[] array = Arrays.copyOfRange(input, 0, k);		buildHeap(array);        // 遍历后面的数，如果小于堆顶元素，就把堆顶换掉，并重新下沉调整堆		for (int i = k; i < len; ++i) {			if (input[i] < array[0]) {				array[0] = input[i];				downAdjust(array, 0, array.length);			}		}		return array[0];	}    // 构造堆	public static void buildHeap(int[] array) {		int startIndex = (array.length - 2) / 2;		for (int i = startIndex; i >= 0; --i) {			downAdjust(array, i, array.length);		}	}	// 调整最大堆	public static void downAdjust(int[] array, int parentIndex, int len) {		int tmp = array[parentIndex];		int childIndex = parentIndex * 2 + 1;		while (childIndex < len) {			if (childIndex + 1 < len					&& array[childIndex + 1] > array[childIndex]) {				childIndex++;			}			if (tmp > array[childIndex]) {				break;			}			array[parentIndex] = array[childIndex];			parentIndex = childIndex;			childIndex = parentIndex * 2 + 1;		}		array[parentIndex] = tmp;	}	public static void main(String[] args) {		int[] array = new int[] { 2, 1, 4, 3, 6, 5, 7, 9, 8 };		int res = GetLeastNumbers_Solution(array, 5);		System.out.print("第K大的元素是：" + res);	}}

构造小顶堆

算法分析：先把数组构造成小顶堆，然后对堆进行k - 1次删除堆顶的操作，最后的堆顶就是要求的第k大元素 。时间复杂度为O(klogN)。

public class Solution {    public int topK_Solution(int [] input, int k) {        int len = input.length;        if (len == 0 || k <= 0 || k > len){            return 0;        }        // 先构造一个堆        bulidHeap(input);        // 将数组进行k - 1次删除堆顶操作        for (int i = len - 1; i > len - k; --i){            int tmp = input[0];            input[0] = input[i];            input[i] = tmp;            downAdjust(input, 0, i);        }        // 返回最后的堆顶        return input[0];    }    public void bulidHeap(int[] array){        int startIndex = (array.length - 2) / 2;        for (int i = startIndex; i >= 0; --i){            downAdjust(array, i, array.length);        }    }     public void downAdjust(int[] array, int parentIndex, int len){            int tmp = array[parentIndex];            int childIndex = parentIndex * 2 + 1;            while (childIndex < len){                if (childIndex + 1 < len && array[childIndex + 1] < array[childIndex]){                    childIndex ++;                }                if (tmp < array[childIndex]){                    break;                }                array[parentIndex] = array[childIndex];                parentIndex = childIndex;                childIndex = parentIndex * 2 + 1;            }            array[parentIndex] = tmp;        }}

使用Java的优先队列

算法分析：其实跟前面用堆是一样的，只不过用了Java中已经封装好的堆，代码更简洁（但这里貌似耗时要长一点，其实这里删除堆顶不用调整，但它这里每次都调整了，所以浪费了时间）

public class Solution {    public int topK_Solution(int [] input, int k) {        int len = input.length;        if (len == 0 || k <= 0 || k > len){            return 0;        }        // 使用优先队列构造一个最大堆，这里用了lambda表达式        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, (o1, o2) -> {            return o2.compareTo(o1);        });        for (int i = 0; i < len; ++i) {            // 往堆中添加数字，直到堆的大小为k            if (maxHeap.size() != k) {                maxHeap.offer(input[i]);            }            // 如果当前元素比堆顶的元素要小，那么将堆顶出队列，将当前元素加入队列(内部会自动调整堆)            else if (input[i] < maxHeap.peek()) {                maxHeap.poll();                maxHeap.offer(input[i]);            }        }        // 返回堆顶元素        return maxHeap.peek();    }}

利用快排的思想

算法分析：基于数组的第k个数来调整，使得最后小于k的数都在k的左边，大于k的数都在k的右边，那么k就是第k大元素

public class Solution {    public int topK_Solution(int [] input, int k) {        int len = input.length;        if (len == 0 || k <= 0 || k > len){            return 0;        }        int start = 0;        int end = len - 1;        int index = partition(input, start, end);        while (index != k - 1){            if (index > k - 1){                end = index - 1;                index = partition(input, start, end);            } else {                start = index + 1;                index = partition(input, start, end);            }        }        return input[k - 1];    }    public int partition(int[] input, int left, int right){        int pivot = left;        int index = pivot + 1;        for (int i = left; i <= right; ++i){            if (input[i] < input[pivot]){                swap(input, i, index);                ++index;            }        }        swap(input, pivot, index - 1);        return index - 1;    }    public void swap(int[] input, int a, int b){        int tmp = input[a];        input[a] = input[b];        input[b] = tmp;    }}