常见的初级排序算法,这次全搞懂

前言

相信所有的程序员刚开始接触到的算法都会是排序算法,因为排序在对数据处理和计算有这重要的地位,排序算法往往是其他算法的基础;本文我们就先从初级排序算法开始学习算法。

排序算法的模板

在开始之前我们先定义一个排序算法通用的模板,在后面的排序算法都会实现这个模板

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;

}

}

}

51CTO
我还没有学会写个人说明!
上一篇

疫情让人们“闻鸡色变” 如何预防人感染禽流感?

下一篇

FAA称SpaceX星际飞船SN9和SN8“爆炸没有危及公众或财产”

你也可能喜欢

评论已经被关闭。

插入图片