排序——冒泡、归并、快速、选择、插入、堆

2024-06-10 02:38
文章标签 选择 快速 归并 排序 插入 冒泡

本文主要是介绍排序——冒泡、归并、快速、选择、插入、堆，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

冒泡排序,O(n²)

原理：遍历集合多次，比较相邻的两个元素，将较大或者较小的元素向后移动，类似于“气泡”一样向上浮动。

	/*** * <p>Title: 基础原理</p>* <p>author : xukai</p>* <p>date : 2017年5月16日 下午2:51:22</p>* @param array*/public static void bubbleSort1(int[] array) {// 1.外层循环，次数为(length-1)for (int i = 1; i < array.length; i++) {// 2.遍历集合，比较相邻元素大小for (int j = 0; j < array.length - i; j++) {if (array[j] > array[j + 1]) {swap(array, j, j + 1);}}System.out.print("第" + i + "次循环执行之后：");print(array);}}

优化：假如在外层循环中，某次循环一次都没有执行swap操作，说明集合已经排序完毕，无需再遍历

	/*** * <p>Title: 某次遍历没有swap（排序完成），那么下一次也不需要遍历</p>* <p>author : xukai</p>* <p>date : 2017年5月16日 下午3:10:03</p>* @param array*/private static void bubbleSort2(int[] array) {boolean needNextPass = true;for (int i = 1; i < array.length && needNextPass; i++) {// 1.假设集合排序完毕needNextPass = false;for (int j = 0; j < array.length - i; j++) {if (array[j] > array[j + 1]) {swap(array, j, j + 1);// 2.假如未被执行，集合排序完毕，外层循环结束needNextPass = true;}}System.out.print("第" + i + "次循环执行之后：");print(array);}}

归并排序，O(nlog(n))

原理：1.将集合平均拆分为两个子集合，对子集合进行归并排序。2.直到子集合中有且仅有一个元素，对两个子集合排序。
这里写图片描述

public class MergeSort {public static void main(String[] args) {int[] array = { 2, 9, 5, 4, 1, 6, 7, 6 };mergeSort(array);}/*** * <p>Title: 1.递归拆除数组</p>* <p>author : xukai</p>* <p>date : 2017年5月17日 下午5:51:16</p>* @param array*/public static void mergeSort(int[] array) {if (array.length > 1) {// 1.左侧数组int[] arrayLeft = new int[array.length / 2];System.arraycopy(array, 0, arrayLeft, 0, array.length / 2);mergeSort(arrayLeft);// 2.右侧数组int arrayRightLength = array.length - arrayLeft.length;int[] arrayRight = new int[arrayRightLength];System.arraycopy(array, array.length / 2, arrayRight, 0, arrayRightLength);mergeSort(arrayRight);// 3.左右侧数组合并int[] temp = merge(arrayLeft, arrayRight);print(temp);// 4.返回已经排序完毕的子数组System.arraycopy(temp, 0, array, 0, temp.length);} else {return;}}/*** * <p>Title: 合并两个数组</p>* <p>author : xukai</p>* <p>date : 2017年5月17日 下午5:51:33</p>* @param arrayLeft* @param arrayRight* @return*/private static int[] merge(int[] arrayLeft, int[] arrayRight) {int[] temp = new int[arrayLeft.length + arrayRight.length];int indexOfLeft = 0;int indexOfRight = 0;int indexOfTemp = 0;while (indexOfLeft < arrayLeft.length && indexOfRight < arrayRight.length) {if (arrayLeft[indexOfLeft] < arrayRight[indexOfRight]) {temp[indexOfTemp++] = arrayLeft[indexOfLeft++];} else {temp[indexOfTemp++] = arrayRight[indexOfRight++];}}while (indexOfLeft < arrayLeft.length) {// 左侧未遍历完temp[indexOfTemp++] = arrayLeft[indexOfLeft++];}while (indexOfRight < arrayRight.length) {// 右侧未遍历完temp[indexOfTemp++] = arrayRight[indexOfRight++];}return temp;}private static void print(int[] array) {for (int i = 0; i < array.length; i++) {System.out.print(array[i] + " ");}System.out.print("\n");}
}

这里需要注意一点代码中的第4步，temp数组为已经排好序的数组，一定要复制给原数组
这里写图片描述

快速排序，O(nlog(n))

原理：任意选择主元元素(默认index=0)，将数组分为两部分，左侧元素小于或等于主元，右侧元素大于主元。对左右两部分递归此操作。
这里写图片描述

/*** @moudle: QuickSort* @version:v1.0* @Description: 快速排序:任意选择主元元素(默认index=0)，将数组分为两部分，左侧元素小于或等于主元，右侧元素大于主元。递归此规则。* @author: xukai* @date: 2017年5月17日 下午6:21:08**/
public class QuickSort {public static void main(String[] args) {int[] array = { 5, 2, 9, 3, 8, 5, 0, 1, 6, 7 };quickSort(array);print(array);}public static void quickSort(int[] array) {quickSort(array, 0, array.length - 1);}private static void quickSort(int[] array, int firstIndex, int lastIndex) {if (firstIndex < lastIndex) {int pivotIndex = partition(array, firstIndex, lastIndex);quickSort(array, firstIndex, pivotIndex - 1);quickSort(array, pivotIndex + 1, lastIndex);}}/*** * <p>Title: partition</p>* <p>author : xukai</p>* <p>date : 2017年5月20日 上午11:39:50</p>* @param array* @param firstIndex* @param lastIndex* @return*/private static int partition(int[] array, int firstIndex, int lastIndex) {int pivot = array[firstIndex]; // 主元int low = firstIndex + 1; // 向前下标int high = lastIndex; // 向后下标while (low < high) {// 当前元素小于等于主元，nextwhile (low <= high && array[low] <= pivot)low++;// 当前元素大于主元，prenextwhile (high >= low && array[high] > pivot)high--;// low,high未移动，array[low]>pivot && array[high] <= pivotif (low < high)swap(array, low, high);}// TODO/*** case:* 1.(array[high]==pivot)=true，next* 2.lastIndex - firstIndex == 1*/while (high > firstIndex && array[high] >= pivot)high--; if (array[high] < pivot) {// pivot放在中间array[firstIndex] = array[high];array[high] = pivot;return high; // 返回主元新下标} else {return firstIndex; // 主元下标}}private static void print(int[] array) {for (int i = 0; i < array.length; i++) {System.out.print(array[i] + " ");}System.out.print("\n");}private static void swap(int[] array, int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;}
}

***我一直没看懂代码中TODO标签下的while循环有什么作用，为什么不删除掉… ***

选择排序，O(n²)

原理：遍历数组，将最小的数放在最前面。遍历剩余元素，持续此操作。

/*** @moudle: SelectSort* @version:v1.0* @Description: 选择排序:遍历数组，将最小的数放在最前面。遍历剩余元素，持续此操作。* @author: xukai* @date: 2017年5月21日 下午2:51:31**/
public class SelectSort {public static void main(String[] args) {int[] array = { 5, 2, 9, 3, 8, 5, 0, 1, 6, 7 };selectSort(array);System.out.println(Arrays.toString(array));}public static void selectSort(int[] array) {// 遍历次数为length - 1;for (int i = 0; i < array.length - 1; i++) {// 1.遍历数组找到min元素int minIndex = i;for (int j = i + 1; j < array.length; j++) {if (array[j] < array[minIndex]) {minIndex = j;}}// 2.swap(array[i],array[index])if (minIndex != i) {int temp = array[minIndex];array[minIndex] = array[i];array[i] = temp;}}}}

这里写图片描述

插入排序，O（n²）

原理：将新元素重复插入已排序好的子数列中

	public static void insertSort(int[] array) {// 遍历未排序数组下标for (int i = 1; i < array.length; i++) {// 遍历已排序完毕的子数组下标for (int j = 0; j < i; j++) {if (array[j] > array[i]) {// j为插入位置int insert = array[i];for (int k = i; k > j; k--) {array[k] = array[k - 1];}array[j] = insert;}}System.out.print("第" + i + "次循环执行之后：");System.out.println(Arrays.toString(array));}}

这里写图片描述

堆排序，O（nlog(n)）

堆特性：

  1. 一颗完整的二叉树(除了最后一层未满且叶子偏左，或每层都是满的)
  2. 每个结点大于或者等于它的子节点

添加结点原理：

  1. 将新元素放置进内部List集合
  2. 将新元素下标作为游标，开始遍历其父结点
  3. 如果大于父结点，swap(子节点，父结点)，执行2和3，直到遍历树完毕。

删除结点原理：

  1. 判断是否为空树,if(true) return null
  2. 将最后的元素放置在index=0(根)，并移除原先元素，temp=root
  3. 遍历树，游标从根开始，找到左右子树中最大值的下标maxIndex
  4. 比较游标和maxIndex的值大小，如果list(cursor)<maxIndex，那么swap
  5. cursor=maxIndex，依旧向下遍历树。直到无swap执行
import java.util.ArrayList;/*** @moudle: 堆类：1.每个结点大于它的所有子结点。2.完全二叉树* @version:v1.0* @Description: TODO* @author: xukai* @date: 2017年5月21日 下午1:58:16** @param <E>*/
public class Heap<E extends Comparable<E>> {private ArrayList<E> list = new ArrayList<>();public Heap() {}public Heap(E[] objects) {for (int i = 0; i < objects.length; i++) {add(objects[i]);}}public void add(E object) {list.add(object);// 1.新元素下标int currentIndex = list.size() - 1;while (currentIndex > 0) {int parentIndex = (currentIndex - 1) / 2; // 当前结点的父结点// 2.新元素大于其父结点,swapif (list.get(currentIndex).compareTo(list.get(parentIndex)) > 0) {E temp = list.get(currentIndex);list.set(currentIndex, list.get(parentIndex));list.set(parentIndex, temp);} else {break;}// 3.向上遍历树currentIndex = parentIndex;}}public E remove() {// 1.判断是否为空树,if(true) return nullif (list.size() == 0)return null;// 2.将最后的元素放置在index=0(根)，并移除原先元素E removeObject = list.get(0);list.set(0, list.get(list.size() - 1));list.remove(list.size() - 1);// 3.从头遍历树int currentIndex = 0;while (currentIndex < list.size()) {// 3.1 maxIndex(left,right)int leftChildIndex = 2 * currentIndex + 1;int rightChildIndex = leftChildIndex + 1;if (leftChildIndex >= list.size())break; // 超出范围int maxIndex = leftChildIndex; // 默认为左子结点，右子节点可能为空if (rightChildIndex < list.size())if (list.get(maxIndex).compareTo(list.get(rightChildIndex)) < 0) maxIndex = rightChildIndex;// 3.2 if(current<maxIndex) swap(current, maxIndex)if (list.get(currentIndex).compareTo(list.get(maxIndex)) < 0) {E temp = list.get(maxIndex);list.set(maxIndex, list.get(currentIndex));list.set(currentIndex, temp);currentIndex = maxIndex;} else {break;}}// 4.返回被删除元素return removeObject;}public int getSize() {return list.size();}
}

排序原理：执行堆的删除操作，即获得堆中最大值。

/*** @moudle: HeapSort * @version:v1.0* @Description: 堆排序* @author: xukai* @date: 2017年5月21日 下午2:38:36**/ 
public class HeapSort {public static void main(String[] args) {Integer[] array = {5, 2, 9, 3, 8, 5, 0, 1, 6, 7};heapSort(array);System.out.println(Arrays.toString(array));}public static Integer[] heapSort(Integer[] array) {// 1.创建一个堆对象，并初始化完毕Heap<Integer> heap = new Heap<>(array);// 2.反向遍历数组，从头开始删除for (int i = array.length - 1; i >= 0; i--) {array[i] = heap.remove();}return array;}
}

总结

JDK中有很多的排序方法实现，例如：Arrays里面的sort方法。
查看代码
动画演示

这篇关于排序——冒泡、归并、快速、选择、插入、堆的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1047005。

相关文章

如何选择适合孤独症兄妹的学校？

如何选择适合孤独症兄妹的学校？

在探索适合孤独症儿童教育的道路上，每一位家长都面临着前所未有的挑战与抉择。当这份责任落在拥有孤独症兄妹的家庭肩上时，选择一所能够同时满足两个孩子特殊需求的学校，更显得尤为关键。本文将探讨如何为这样的家庭做出明智的选择，并介绍星贝育园自闭症儿童寄宿制学校作为一个值得考虑的选项。 理解孤独症儿童的独特性 孤独症，这一复杂的神经发育障碍，影响着儿童的社交互动、沟通能力以及行为模式。对于拥有孤独症兄
阅读更多...
电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

在日常使用电脑的过程中，我们经常会遇到这样的情况：一不小心，桌面上的某个重要文件被删除了。这时，大多数人可能会感到惊慌失措，不知所措。 其实，不必过于担心，因为有很多方法可以帮助我们找回被删除的桌面文件。下面，就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件，并且还没有进行其他操作，那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c
阅读更多...
C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

哈喽，你好啊，我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记，这是第6篇； 接下来实现实时显示当前选中红球数量，蓝球数量； 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时，在对应的位置显示实时已选择的红球、蓝球的数量； 02 标签名称 分别设置Label标签名称为：lblRedCount、lblBlueCount
阅读更多...
透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

引言 随着时间的发展，大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用，随着人们期望的不断增加，目标也发生了巨大的变化。在短短的几个月的时间里，人们对大模型的认识已经从对其zero-shot能力感到惊讶，转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构（例如Transformer）对海量的、多种多样的数据分布进行建模得到，它包含了大量的先验
阅读更多...
hdu 1285（拓扑排序）

hdu 1285（拓扑排序）

题意： 给各个队间的胜负关系，让排名次，名词相同按从小到大排。 解析： 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式，对一个有向无回路图进行拓扑排序后，所有的顶点形成一个序列，对所有边(u,v)，满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上，某些工程完成后，另一些工程才能继续，此时
阅读更多...
cross-plateform 跨平台应用程序-03-如果只选择一个框架，应该选择哪一个?

cross-plateform 跨平台应用程序-03-如果只选择一个框架，应该选择哪一个?

跨平台系列 cross-plateform 跨平台应用程序-01-概览 cross-plateform 跨平台应用程序-02-有哪些主流技术栈？ cross-plateform 跨平台应用程序-03-如果只选择一个框架，应该选择哪一个? cross-plateform 跨平台应用程序-04-React Native 介绍 cross-plateform 跨平台应用程序-05-Flutte
阅读更多...
hdu 4565 推倒公式+矩阵快速幂

hdu 4565 推倒公式+矩阵快速幂

题意 求下式的值： Sn=⌈ (a+b√)n⌉%m S_n = \lceil\ (a + \sqrt{b}) ^ n \rceil\% m 其中： 0<a,m<215 0< a, m < 2^{15} 0<b,n<231 0 < b, n < 2^{31} (a−1)2<b<a2 (a-1)^2< b < a^2 解析 令： An=(a+b√)n A_n = (a +
阅读更多...
v0.dev快速开发

v0.dev快速开发

探索v0.dev：次世代开发者之利器 今之技艺日新月异，开发者之工具亦随之进步不辍。v0.dev者，新兴之开发者利器也，迅速引起众多开发者之瞩目。本文将引汝探究v0.dev之基本功能与优势，助汝速速上手，提升开发之效率。 何谓v0.dev？ v0.dev者，现代化之开发者工具也，旨在简化并加速软件开发之过程。其集多种功能于一体，助开发者高效编写、测试及部署代码。无论汝为前端开发者、后端开发者
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2