常见排序算法总结(冒泡排序、快速排序、选择排序、插入排序)——Java语言(一)

前言

排序算法是最基本的算法之一,为此衍生出很多种的排序算法,而不同的排序算法具有不同的使用环境,为此掌握几种常见的排序算法是作为一个精致的程序员必不可少的技能。本文主要是介绍常见的四种排序算法的思想以及Java实现。

2018年9月13日11:27:56更新:

更新内容:

* 重置原有算法,按照一种更加容易理解的白话文说明各种算法的特点。
* 增加时间复杂度概念,分析时间复杂度。

序列文章:

常见算法

冒泡排序(Bubble Sort)

冒泡排序(英语:Bubble Sort,台湾另外一种译名为:泡沫排序)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 ——来源《维基百科》

冒泡排序算法核心思想

假如有n个无序的数需要从小到大进行排序,那么使用冒泡排序一定是这样做的:

  • 比较相邻的元素。如果第一个比第二个大,就交换他们两个。

  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一(即为0和1比较,1和2比较,n-2和n-1比较)。这步做完后,最后的元素会是最大的数。

  • 针对下标为 0-(n-2)重复以上的步骤。

  • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

图示例:

{mdFileName}-20183914350

举例

比如对于8 4 9 2 5 这组无序序列来说:
算法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
* 冒泡函数
*
* @param array 目标数组
*/
public static void bubbleSort(int array[]) {
//输入合法性校验,如果是空数组或者数组只有一个数,那么不需要排序,直接返回
if (array == null || array.length < 2) {
return;
}
//外层循环控制需要排序的数列,从0到i
for (int i = array.length - 1; i > 0; i--) {
//内层循环进行比较
for (int j = 0; j < i; j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
}
}
}
}

/**
* 交换函数
*
* @param array 目标数组
* @param i 交换的数组的下标
* @param j 交换的数组的下标
*/
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}

此算法的执行思想是:

外层循环控制的是这个数组中需要排序的序列,第一趟之后,需要排序的序列的下标就是从0到n-2。而内层循环通过j和j+1进行比较,如果array[j]>array[j+1],那么就进行交换,通过array.length次的遍历,每一次都能将最大的排列到数组序列的最后一个,这样就能够完成排序。

当然,此类算法还有许多变形,比如下面:

1
2
3
4
5
6
7
8
9
10
for (int i = 0; i < arr.length-1; i++) {
for (int j = arr.length-1; j >i ; j--) {
if (arr[j]>arr[j-1]) {
int temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;

}
}
}

此算法的思想是:从后向前进行比较,外层循环只是控制循环的次数,内层循环控制交换。这样一来,始终能保持在最前面的数是符合排序规则的。

无论是怎样的变形,都是像吐泡泡一样,将符合条件的吐出来,然后没有吐出来的进行比较,直到找到合适的泡泡然后吐出来。

时间复杂度

时间复杂度这个概念很复杂,是为一个算法流程中的,常数操作数量的指标。对于这样一个O(N),是通过取极限的方式得到的,总的来说,忽略低阶项,忽略高阶项的系数项。

在常数操作数量的表达式中,只要高阶项,不要低阶项,不要高阶项的系数,剩下的部分即为f(N),那么时间复杂度为O(f(N))。

那么对于冒泡算法来说(ps:该算法基本已经绝迹,因为时间复杂度相对较高,消耗的系统资源较大),时间复杂度的计算方式如下:

对于这样一个算法流程来说,需要遍历的次数为:n+(n-1)+(n-2)+···2+1,这是一个等差数列,对于等差数列进行求和,得到的是:aN^2 +bN+c (a,b,c)为常数项。这里用到了数学的取极限的方法,这里的bN+c可以忽略,对于N很大来说,a对aN^2的影响不是特别大,可以忽略,在这里得到的时间复杂度为O(N^2),读作(big o N^2)。

选择排序(Selection Sort)

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对 n个元素的表进行排序总共进行至多 n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。 ————来源《维基百科》

实例介绍

图片动画演示

图片来源——维基百科
红色表示当前最小值,黄色表示已排序序列,蓝色表示当前位置。
以上动画演示的是数组:a[]={8, 5, 2, 6, 9, 3, 1, 4, 0, 7};接下来会结合动画进行说明:

  • 遍历数组a[0,n] (n为数组的长度),找到里面最小的数0,放到最前面,数组变为:a[]={0,5,2,6,9,3,1,4,8,7};
  • 遍历数组a[1,n],找到最小的数1,放到数组下标为1的位置,数组变为a[]={0,1,2,6,9,3,5,4,8,7};

重复以上步骤,最终数组变为:a[]={0,1,2,3,4,5,6,7,8,9}。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* 选择排序
*
* @param array 目标数组
*/
public static void selectionSort(int[] array) {
//数组输入参数合法性校验
if (array == null || array.length < 2) {
return;
}
for (int i = 0; i < array.length; i++) {
int minIndex = i;
for (int j = i + 1; j < array.length; j++) {
minIndex = array[j] < array[minIndex] ? j : minIndex;
}
swap(array, minIndex, i);
}
}

/**
* 交换
* @param array 目标数组
* @param minIndex 当前找到的最小的数的下标
* @param i 要交换的数的下标
*/
private static void swap(int[] array, int minIndex, int i) {
int temp = array[minIndex];
array[minIndex] = array[i];
array[i] = temp;
}

时间复杂度

可以看下上面的图示,可以看到,每次都会去遍历这样一个数组,遍历的次数为(n-1+(n-2)+····2+1。这还是一个等差数列,由于这个算法是写死的,什么意思呢,就是说这样一个算法,如果这是一个完全有序的数组,要进行排序,它还是会对每一个数都遍历一次,找到这个序列中最小的,放到合适的位置上去。与数组是否有序无关。

从上面的分析可以知道,这个时间复杂度还是一个等差数列,和上面的冒泡的分析一样,这里的时间复杂度为O(N^2)

快速排序(Quick Sort)

快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。快速排序采用“分而治之、各个击破”的观念。 ————来源《维基百科》

步骤为:

  • 从数列中挑出一个元素,称为”基准”(pivot),
  • 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任何一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  • 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。
  • 递归到最底部时,数列的大小是零或一,也就是已经排序好了。这个算法一定会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

举例

比如对于22, 5 ,85, 65 ,21 ,99 ,66这组无序序列来说。

{mdFileName}-201839164140

在本例子中,选取的是数组中的第一个22作为基准,采用分而治之的思想,将数组小于和大于基准的数分为两组,再采用递归的方法再进行排序,直到排序完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private static void quick_sort(int[] a, int l, int r) {
if (l < r) {
int i = l, j = r, x = a[l];
while (i < j) {
while (i < j && a[j] >= x) {//先从后面往前面找
j--;
}
if (i < j) {//如果找到比基准小的数,将这个比基准小的数放到之前的基准所在的位置去
a[i] = a[j];
}
while (i < j && a[i] < x) {//再从前面往后面找
i++;
}
if (i < j) {//如果找到了比基准大的数,那么将这个比基本大的数放到上一个空出来的位置去
a[j] = a[i];
}
}
a[i] = x;
quick_sort(a, l, i - 1);//递归调用,对基准左边的数进行排序
quick_sort(a, i + 1, r);//对基本右边的数进行排序
}
}

插入排序(Insertion Sort)

插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序,因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。 ————来源《维基百科》

排序思想

将一组数据分为两组,分别为有序组和无序组。每次从无序组中取出最前面的数和有序组的最后一个数进行比较,为这个数在有序组中找到一个合适的位置,这样始终保持着有序组中的数始终是有序的,直到遍历到最后一个。

想象下斗地主,摸牌的之前自己手中的牌是不是有序的,对吧,当你又摸起来了一张牌的时候,是不是要找它的合适位置,是不是就相当于要进行一次遍历,然后把牌插入到指定的位置。这就是插入排序。

{mdFileName}-2018310111715
图片来源于网络

举例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* 插入排序
*
* @param array 目标数组
*/
public static void insertSort(int[] array) {
// 参数合法性校验
if (array == null || array.length < 2) {
return;
}
//外层循环,控制的需要进行插入的数的位置
for (int i = 1; i < array.length; i++) {
//内层循环,将当前这个数拿到有序祖列中进行遍历,找到它的合适位置
for (int j = i - 1; j >= 0 && array[j] > array[j + 1]; j--) {
swap(array, j, j + 1);
}
}
}

/**
* 交换函数
*
* @param array 目标数组
* @param i 需要交换的下标位置
* @param j 需要交换的下标位置
*/
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}

总结

四种最常见的排序算法的相关指标如下:
{mdFileName}-201831012532 不同的算法具有很多种的变形,比如冒泡,可以从序列前面开始,也可以从后面开始,其原理都一样。

-------------The End-------------

本文标题:常见排序算法总结(冒泡排序、快速排序、选择排序、插入排序)——Java语言(一)

文章作者:Dimple

发布时间:2018年03月09日 - 13:03

最后更新:2018年09月17日 - 20:09

原始链接:http://www.bianxiaofeng.com/2018/03/09/2018-3-9-135602/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

na,给我一个棒棒糖!
0%