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

前言

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

常见算法

冒泡排序(Bubble Sort)

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

冒泡排序算法核心思想

  • 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  • 针对所有的元素重复以上的步骤,除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

{mdFileName}-20183914350

举例

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

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

此算法的执行思想是:外层循环i是控制第1、2···个数,然后把这第1、2···个数依次与后面的数进行比较,如果后面的数不符合排序规则,那么就进行替换。这样一来,能够保证外层循环已经循环过的数始终是符合排序规则的。

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

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;

}
}
}

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

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

快速排序(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
static void InsertionSort(int num[]) {
int j=0,temp=0;//定义变量,temp用于保存要进行比较的数(未排序队列的第一个数)
for (int i = 1; i < num.length; i++) {//遍历(之所以是从数组下标1开始是因为数组下标为0的数只有一个,本身就是一个有序组)
temp=num[i];//保存未排序队列的第一个数,这个时候相当于数组下标为i的位置为坑,需要找到一个合适的数来填这个坑
j=i-1;//j定位已经排序好了的队列的最后一个数的下标
while (j>=0&&num[j]>temp) {//j>=0防止数组越界。num[j]>temp是交换条件
num[j+1]=num[j];
j--;
}
num[j+1]=temp;//这里是j+1不是j的原因是执行了上一步j--之后,j比本身应该在的位置少1,所以+1
}
}

选择排序(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
static void SelectionSort(int a[]) {
int k = 0, temp = 0;// 其中k用于记录符合条件的数组的下标,temp用于交换数据作为中间变量
for (int i = 0; i < a.length - 1; i++) {// 这里减一的原因是,之前的数都是分别和这个最后一个数比较的,所以最后一个数一定是符合排序规则的
for (int j = i; j < a.length - 1; j++) {
if (a[j] < a[i]) {
k = j;// 记录下符合排序规则的数的下标
}
}
// 交换
temp = a[i];
a[i] = a[k];
a[k] = temp;
}

}

总结

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

-------------本文结束感谢您的阅读-------------
na,给我一个棒棒糖!