基本排序:从忘记到捡起(一)——冒泡与快排

数据结构与算法不能说是一个程序员工作中的必杀技(虽然我还是个很稚嫩的猴子这么说好像不太妥),但是连最基本的排序算法都忘记了都不好意思说自己是只猴子,对于算法数据结构这块,当年虽说写起来呼呼就是一阵风,但算法的小船说翻就翻,有空还是要回头搞搞基础建筑才行哇!


这篇文章将捡起两个排序算法,分别是。。题目说了。
为了专注理解,数据无伤大雅,统一用以下数据,统一从小到大排序。

1
int data[]={1,9,3,7,5,10,24,66};

冒泡排序

概述

大数往下沉,小数浮上来。

原理

在原始数据中从头到尾对相邻的数进行比较,如果后一个比前一个大,就交换顺序,嗯,大致就这样了,不过这还不行,这样会有一个问题,这样交换只是一趟下来相邻的交换,并不能把最大的数沉下去,所以外面还需要一个东东来控制趟数。

代码来了

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

/**
*
* @author KevinWu
*
*/
public class BubbleSort {
private int data[];

public BubbleSort(int data[]) {
this.data = data;
sort();
}

private void sort() {
int temp = 0;
for (int i = 0; i < data.length - 1; i++) {
for (int j = 0; j < data.length - 1 - i; j++) {
if (data[j] > data[j + 1]) {
temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
}
}
}
}

public int[] getSortData() {
return data;
}

}

快排

概述

两头缩。

插播小故事

我讲个小故事,话说一个很在意身高的班级里面,军训排队,一条乱序的队伍需要按照身高排好。A排头,但他觉得他是最高的应该排尾,于是A走到排尾,发现果然比最后一个同学B高,于是强行占着倒数第一个位置不走了,B同学只能委屈跑到排头,但是很不服,他就跟排第二的C同学说,A好拽,他赶我过来,还说你没他高,然后排第二的C就不服了,过去一比,卧槽果然没A高,于是也尴尬的回来了,一样很不服,跟排第三的D说,A说你没他高,D当然不服,跑去排尾跟A一比,结果是D比A高出一头,嘿嘿,D当然站最后,A也无奈的跑回来排第三个位置了,A回来想想挺不服的,于是就想第一高不是我,第二高总是了吧,于是又跑回倒数第二找到E,一比发现居然也没有倒数第二的E高,这就不服了,找倒数第三的F比,哎,终于比F高了,F也无奈,只能跑到排头第三的位置而让出倒数第三的位置,A就站到倒数第三位置去了,但F想想,自己也没那么矮吖,于是打算去到倒数第四位置找G。。。
好吧打字打的我有点累,后面脑补吧。

原理

选择一个数作为基准数,一般选择第一个,假设它最大,通过一趟扫描,把排序的数分成两部分,一部分小于基准数,一部分大于或者等于(特别注意,这是一个不稳定的排序算法,要考虑等于,本人亲身掉过坑)基准数,这个时候这个基准数就处在正确的位置了,然后再对接下来的数执行同样的操作。

代码来了

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
34
35
36
37
38
39
40
41
42
43
44
45
/**
*
* @author kevinwu
*
*/
public class QuickSort {
private int data[];

public QuickSort(int data[]) {
this.data = data;
sort();
}

private void sort() {
recursionSorting(data, 0, data.length - 1);

}

private void recursionSorting(int[] data, int left, int right) {
if (left < right) {
int modelIndex = getModelIndex(data, left, right);
recursionSorting(data, left, modelIndex - 1);
recursionSorting(data, modelIndex + 1, right);
}
}

private int getModelIndex(int[] data, int left, int right) {
int model = data[left];// 这个就是鸡数,鸡佬的鸡
while (left < right) {
while (left < right && data[right] >= model)
right--;
data[left] = data[right];// 比鸡数小的移到左边
while (left < right && data[left] <= model)
left++;
data[right] = data[left];// 比鸡数大的移到右边
}
data[left] = model;
return left;
}

public int[] getSortData() {
return data;
}

}

好了,不给测试类了,虽然我自己默默测试了。
顺便提一句,其实严谨点抽出来个排序接口,下面再定义各种排序类,会比较好,好吧其实这是在研究算法,研究算法,算法,法!

文章作者: Kevin Wu
文章链接: https://kevinwu.cn/p/bb692402/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 KevinWu的博客
支付宝打赏