常见的初级排序算法，这次全搞懂
source link: http://developer.51cto.com/art/202102/646536.htm
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
前言
相信所有的程序员刚开始接触到的算法都会是排序算法，因为排序在对数据处理和计算有这重要的地位，排序算法往往是其他算法的基础;本文我们就先从初级排序算法开始学习算法。
排序算法的模板
在开始之前我们先定义一个排序算法通用的模板，在后面的排序算法都会实现这个模板
public interface SortTemplate {
void sort(Comparable[] array);
default void print(Comparable[] array) {
for (Comparable a : array) {
System.out.print(a + " ");
}
}
default boolean less(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
default void exch(Comparable[] array, int i, int j) {
Comparable tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
Comparable: 为了让我们实现的排序算法更加的通用，可以排序任意的对象，所以我们这里使用了Comparable数组
sort: 不同的排序算法实现的方式不一样，子类自己去实现
less: 定义的公用方法，如果a < b就返回true
exch: 定义的公用方法，交换数组中的两个对象
print: 打印出数据中的每个元素
选择排序
算法实现的思路：
首先找到数组中的最小元素，
其实将它和数组中的第一个元素进行交换，这样就排定了一个元素;
再次找出剩余元素中最小的元素与数组中的第二个元素进行交换，如此反复直到所有元素都是有序的
代码实现：
public class SelectionSort implements SortTemplate {
@Override
public void sort(Comparable[] array) {
int length = array.length;
for (int i = 0; i < length; i++) {
int min = i;
for (int j = i + 1; j < length; j++) {
if (less(array[j], array[min])) {
min = j;
}
}
exch(array, i, min);
}
}
}
假如输入的数组是有序的，我们会发现选择排序运行的时候和未排序的时间一样长!
对于N个元素的数组，使用「选择排序的时间复杂度是O(n2)」
选择排序的是「数据移动最少」的，交换的次数与数组的大小是线性关系，N个元素的数组需要N次交换
冒泡排序
算法实现的思路：
比较相邻的两个元素，如果前一个比后一个大，那么就交换两个元素的位置
对每一组相邻的元素执行同样的操作，直到最后一个元素，操作完成之后就可以排定一个最大的元素
如此往复，直到数组中所有的元素都有序
图片
代码实现：
public class BubbleSort implements SortTemplate {
@Override
public void sort(Comparable[] array) {
int length = array.length - 1;
for (int i = 0; i < length; i++) {
for (int j = 0; j < length - i; j++) {
if (less(array[j + 1], array[j])) {
exch(array, j, j + 1);
}
}
}
}
}
对于N个元素的数组，使用「冒泡排序的时间复杂度是O(n2)」
插入排序
想象我们在玩扑克牌时，整理扑克牌都是把每一张插入到左边已经排好序的牌中适当的位置。插入排序的思路类似
算法实现的思路：
初始默认第一个元素就是有序的，当前索引的位置从0开始
先后移动当前索引的位置，当前索引位置左边的元素是有序的，从后往前开始扫码与当前索引位置元素进行比较
当确定当前索引位置上的元素在左边有序适合的位置之后，插入到该位置上
如果当确定当前索引位置上的元素大于了已排序的最后一个元素，那么当前索引位置直接往后移动
如此反复，直到所有元素有序
图片
代码实现：
public class InsertionSort implements SortTemplate {
@Override
public void sort(Comparable[] array) {
int length = array.length;
for (int i = 1; i < length; i++) {
for (int j = i; j > 0 && less(array[j], array[j - 1]); j--) {
exch(array, j, j - 1);
}
}
}
}
从代码的实现我们可以看出，当遇到了当前索引的元素大于了左边有序数组的最后一个元素时，内层循环就直接结束了，所以所我们排序的数组中存在着部分有序，那么插入排序算法会很快。
考虑最糟糕的情况，如果输入数组是一个倒置的，那么插入排序的效率和选择排序一样，「时间复杂度是O(n2)」
希尔排序
对于大规模的乱序数组插入排序很慢，是因为它只交换相邻的元素，元素只能一点一点的从数组中移动到正确的位置;插入排序对于部分有序的数组排序是的效率很高;
希尔排序基于这两个特点对插入排序进行了改进;
算法实现的思路
首先设置一个步长h用来分隔出子数组
用插入排序将h个子数组独立排序
减小h步长继续排序子数组，直到h步长为1
当步长为1时就成了普通的插入排序，这样数组一定是有序的
希尔排序高效的原因，在排序之初，各个子数组都很短，子数组排序之后都是部分有序的，这两种情况都很适合插入排序。
图片
代码实现：
public class ShellSort implements SortTemplate {
@Override
public void sort(Comparable[] array) {
int gap = 1;
int length = array.length;
while (gap < length / 3) {
gap = 3 * gap + 1;
}
while (gap >= 1) {
for (int i = gap; i < length; i++) {
for (int j = i; j >= gap && less(array[j], array[j - gap]); j -= gap) {
exch(array, j, j - gap);
}
}
gap = gap / 3;
}
}
}
Recommend
-
48
-
63
一、排序算法 1、冒泡排序（Bubble Sort） 定义：是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就...
-
13
本文总结了常见高频的关于排序的算法考察。 1.冒泡排序 冒泡排序的思想是元素两两比较，将较大或者较小的元素往一端进行移动 public static void bubble(int[] array) { for (int i = 0; i < arra...
-
11
图示阅读的顺序为从左到右，从上到下 近期在看一些算法相关的知识，这里总结整理下常见排序算法的 JavaScript 实现，并添加图解方便理解。 下面是一些代码中会用到的公共方法，为了避免代码...
-
8
本文已被Github仓库收录 https://github.com/silently9527/JavaCore 微信公众号：贝塔学Java 前言 前几天写了一篇《JVM性能调优实战：让你的IntelliJ Ide...
-
12
排序算法是数组相关算法的基础知识之一，它们的经典思想可以用于很多算法之中。这里详细介绍和总结 7 种最常见排序算法，并用 Go 做了实现，同时对比这几种算法的时间复杂度、空间复杂度和稳定性 。后一部分是对 Go 标...
-
10
JavaScript 之常见算法排序 冒泡排序即数组从头到尾，依次比较相邻两数的大小，不符合顺序则交换位置，一直循环直到排序完成。如果是升序排序，那么每一轮的一系列比较和交换之后，最大那个...
-
3
联系方式(qq)：623847465 gitee(码云)： Mercury. (zzwlwp) - Gitee.com 键盘在左，鼠标在右，他们只要一个文本文件就可以创造一个未来。😎 你与程序员或许只差左...
-
4
一文全搞懂postgresql的角色 精选 原创 进击的CJR 2022-10-18 15:30:22...
-
6
对比几种常见的排序算法@0xinhua 发布于 2017年12月13日计算机科学里，排序算法是最基础算法之一，排序的方式有很多种，例如我们常见的冒泡排序、插入排序、快排等，这类需要对系列值进行比较的方法，称为基于比较排序...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK