算法专题:排序

排序


稳定性

一个排序算法的稳定性是指,如果a=b,排序前a在b前面,那么排序后a也要在b的前面。即排序后元素的相对位置不变

简单来说:

  • 如果一个排序算法会将某个元素单独提到某个位置,那么它就是不稳定的
  • 如果一个排序算法只涉及两两相邻元素之间的交换,那么它就是稳定的
  1. 稳定排序:冒泡排序插入排序希尔排序归并排序
  2. 不稳定排序:选择排序快排堆排序

1.选择排序(O(N^2)

  • 选择排序(Selection Sort)每次排序时,从未排序序列中“选择”一个元素加入排序序列,因此得名。
  • 选择排序需要两次遍历 —— 第一遍是遍历所有元素,确认已排序的序列范围[0,i);第二遍是遍历所有未排序序列[i,lastIndex],每次将当前位置与队首(i)元素比较,选择最小元素,交换到队首,所以选择排序的时间复杂度是O(N^2)
  • 选择排序是不稳定排序,因为存在将元素单独提到某个位置的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//选择排序
public static int[] selectionSort(int[] in) {
int lastIndex = in.length - 1; //即:循环遍历次数
for (int i = 0; i <= lastIndex; i++) { //每次遍历,将最小元素浮动到最左边
//0~i是已排序序列,i~lastIndex是未排序序列,将未排序中的最小元素放在i位置
for(int j = i; j <= lastIndex; j++) {
//默认in[i]是最小元素,如果in[j]小于in[i],则交换
if (in[j] < in[i]) { //如果i=j,那么in[i]=in[j]
//所以可以保证in[i]、in[j]是不同对象,可以通过异或进行交换
in[i] = in[i] ^ in[j];
in[j] = in[i] ^ in[j];
in[i] = in[i] ^ in[j];
}
}
}
return in;
}

选择排序 & 插入排序 的区别:
选择排序是每次从未排序序列中选择最小/最大的元素,加入已排序序列
插入排序是每次按顺序从未排序序列中选择一个元素,加入已排序序列中的合适位置
也就是说,选择排序遍历的未排序序列,插入排序遍历的已排序序列


2.冒泡排序(O(N^2)

  • 冒泡排序(Bubble Sort)每次排序时,将未排序序列最大元素“浮动”到尾部,因此得名。
  • 冒泡排序需要两次遍历 —— 第一遍是遍历所有元素,确认已排序的序列范围[lastIndex - i, lastIndex];第二遍是遍历所有未排序序列(0, lastIndex - i),相邻元素两两比较,将最大元素浮动到队尾,所以冒泡排序的时间复杂度是O(N^2)
  • 冒泡排序是稳定排序,因为只涉及相邻元素两两比较
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//冒泡排序
public static int[] bubbleSort(int[] in) {
int lastIndex = in.length - 1;
for (int i = 0; i <= lastIndex; i++) {
//[lastIndex - i,lastIndex]是排好序的序列
//[0,lastIndex - i)是未排好序的序列
for(int j = 0; j <= lastIndex - i - 1; j++) {
//与选择排序不同,冒泡排序是两两相邻元素比较后交换
//将较大的交换到后面
if (in[j + 1] < in[j]) { //不同元素异或交换
in[j + 1] = in[j] ^ in[j + 1];
in[j] = in[j] ^ in[j + 1];
in[j + 1] = in[j] ^ in[j + 1];
}
}
}
return in;
}

2.1 冒泡排序优化:交换标志位

对冒泡排序的优化是加入一个交换标志位,如果某一次循环中没有进行数据交换,说明剩余的序列已经是有序的了,可以不再进行后续的循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//优化冒泡排序——加入交换标志位
public static int[] flagBubbleSort(int[] in) {
//标志位:本趟排序是否进行了交换
//如果本趟排序没有进行元素交换,说明已经有序了,可以提前结束循环
boolean exchange;
int lastIndex = in.length - 1;
for (int i = 0; i <= lastIndex; i++) {
exchange = false;
//[lastIndex - i,lastIndex]是排好序的序列
//[0,lastIndex - i)是未排好序的序列
for(int j = 0; j <= lastIndex - i - 1; j++) {
//与选择排序不同,冒泡排序是两两相邻元素比较后交换
//将较大的交换到后面
if (in[j + 1] < in[j]) { //不同元素异或交换
in[j + 1] = in[j] ^ in[j + 1];
in[j] = in[j] ^ in[j + 1];
in[j + 1] = in[j] ^ in[j + 1];
exchange = true; //发生了交换
}
}
if(!exchange) break; //无交换直接退出循环
}
return in;
}

3.插入排序(O(N^2)

在形容插入排序时,一般都会类比摸扑克。你的手牌就是已排序序列,牌堆就是未排序序列,每次摸牌时会选择手排中的合适位置插入。
我的习惯就是强迫按顺序插好牌 - - ||| ,后来我才发现其他孩子摸牌根本不会像我一样,他们都是一把抓在手里面的,所以每次玩扑克他们都要等我抓好牌=====( ̄▽ ̄*)b

  • 插入排序(Insertion Sort)的原理就是将序列分为两个部分,一部分是已排序序列,另一部分是未排序序列,每次从未排序序列中选择一个元素插入已排序序列中的合适位置
  • 插入排序需要两次循环——第一次是遍历所有元素,确定已排序序列[0,i);第二次是遍历所有已排序序列[0,i),将位置i的元素插入已排序序列的合理位置——由于遍历的序列是已经排好序的,所以这一步只需要用到一个临时变量。所以插入排序的时间复杂度是O(N^2)
  • 使用一个临时变量temp存储位置i的元素。从j=i位置开始向前遍历,如果in[j] > temp,那么j--;如果in[j] <= temp,那么交换j位置元素和temp,然后j--,继续比较in[j]temp
  • 插入排序是稳定性排序,因为只涉及到相邻元素两两比较
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//插入排序
public static int[] insertionSort(int[] in) {
int lastIndex = in.length - 1;
//从1开始遍历,是默认最开始的已排序序列就是第一个元素,index=0
for (int i = 1; i <= lastIndex; i++) {
int temp = in[i]; //待比较元素
//注意i不能比1小,否则就会数组越界
while (i >= 1 && in[i - 1] > temp) { //已排序序列[0,i),最大下标i - 1
//i - 1位置元素大于待比较元素,i - 1位置元素后移
in[i] = in[i - 1];
i--;
}
//退出循环说明找到了合适的位置
in[i] = temp;
}
return in;
}

3.1 希尔排序(O(NlogN))/缩小增量排序

  • 希尔排序(Shell Sort)是一种改进的插入排序,也成为缩小增量排序,1959年由Donald Shell提出。希尔排序采用了分治的思想,将原序列分为若干个子序列,对子序列分别进行插入排序,所以它的时间复杂度也理所应当是O(NlogN)
  • 初始增量gap = len / 2,随后每次循环gap = gap / 2,直到减为1,循环终止。增量gap的意义是将序列分为多少子序列。
  • 希尔排序存在非相邻元素交换位置,所以希尔排序是不稳定排序


如图:

  1. 初始分组gap = len / 2 = 5,将原序列分为5组,要求每组元素之间间隔尽可能大,所以是{i, i + gap, i + 2 * gap, …, i + n * gap}
  2. 对5组子序列分别进行插入排序,将较小的元素交换到前面
  3. 交换完后,gap /= 2,将原序列重新分为2组,要求每组元素之间间隔尽可能大,所以是{i, i + gap, i + 2 * gap, …, i + n * gap}
  4. 对2组子序列分别进行插入排序,将较小的元素交换到前面
  5. gap = 2 / 1 = 1,进行最后一次插入排序,结束循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//希尔排序
public static int[] shellSort(int[] in) {
int gap = in.length >> 1; //初始值,gap = len / 2
while (gap > 0) {
//从gap开始是因为默认[0,gap)是排好序的
//即每个子序列第一个元素是排好序的,一共gap个元素
//将序列分为gap组,对子序列进行插入排序
for (int i = gap; i < in.length; i++) {
int temp = in[i];
//限制了gap>0,所以只需要 i-gap>=0 而非 1
while ((i - gap >= 0) && (in[i - gap] > temp) ) {
in[i] = in[i - gap];
i -= gap; //每次跨度为一个gap
}
//退出循环说明找到了合适位置
in[i] = temp;
}
gap = gap >> 1; //gap = gap / 2
}
return in;
}

希尔排序 vs 插入排序:
插入排序是稳定的,希尔排序不稳定;
希尔排序比较次数和移动次数都要明显小于插入排序,N越大越明显
希尔排序不适用于链式结构


4.归并排序(O(NlogN)

  • 合并两个有序子序列的过程:创建一个和两个字序列长度和等长的序列,分别用一个指针指向两个子序列的头部,将两个子序列头部较小的那个加入到新序列,最后一个序列全部被加入新序列,就可以把另一个序列剩下的元素加入新序列。所以归并排序需要额外的内存空间
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
//合并两个有序子序列
//@params: left[] 左子序列
//@params: right[] 右子序列
public static void merge(int[] left, int[] right) {
//结果序列,用于合并两个子有序序列
int[] rst = new int[left.length + right.length];
//左子序列、右子序列、总序列当前位置
int l = 0, r = 0, curr = 0;
//遍历,直到某个子序列被遍历完,将较小的放前面
while (l < left.length && r < right.length) {
if (left[l] < right[r]) {
rst[curr] = left[l];
l++;
curr++;
}else{
rst[curr] = right[r];
r++;
curr++;
}
}
//剩余序列直接加入结果序列
while(l < left.length) {
rst[curr] = left[l];
l++;
curr++;
}
while (r < right.length) {
rst[curr] = right[r];
r++;
curr++;
}
return rst;
}
  • 归并排序(Merge Sort)利用了分治的思想,将序列不断进行二分,直到每组子序列只剩下两个元素(“分”),然后对这两个元素进行排序(“治”),最后将所有子序列两两进行合并,合并时重新排序(“合”),所以时间复杂度是O(NlogN)
  • 归并排序只涉及相邻元素之间的交换,所以是稳定性排序

1
2
3
4
5
6
7
8
9
10
11
12
//归并排序:递归地使用二分法,将一个序列分解为两个子序列,直到子序列只剩下一个元素
//@params: in[]
public static int[] mergeSort(int[] in) {
//退出递归的条件:子序列只剩下一个元素
if(in == null || in.length < 2) return in;
int mid = in.length >> 1; //从中间将序列切分
//Arrays.copyOfRange(int[] a, int from, int to); 复制范围[from,to)
int[] left = Arrays.copyOfRange(in, 0, mid); //不包括mid
int[] right = Arrays.copyOfRange(in, mid, in.length);
//递归调用mergeSort,然后将结果merge合并
return merge(mergeSort(left), mergeSort(right) );
}

测试:

1
2
3
int[] in = {999, 1, 2, 4, 3, -1, 0, 0};
System.out.println("归并排序: " + Arrays.toString(mergeSort(in)));
//归并排序: [-1, 0, 0, 1, 2, 3, 4, 999]

5.快速排序(O(NlogN)

参考了https://cloud.tencent.com/developer/article/1403566,说的很详细。

  • 快速排序(Quick Sort)的中心思想是每次选取一个基准值(pivot),然后通过比较与交换,使得pivot左边的元素都小于pivotpivot右边的元素都大于pivot;然后再通过二分法,对pivot左右的子序列分别进行快排。所以快排的时间复杂度是O(NlogN)
  • pivot一般直接选择最左元素
  • 交换pivot左右元素用到了快慢指针法——快指针从右往左遍历,直到找到比pivot小的元素;慢指针从左往右遍历,直到找到比pivot大的元素。由于我们的目的是让左边的更小,右边的更大,所以我们将快慢指针元素进行交换(交换之前要判断慢指针是否超过了快指针)。

如下图:

  1. 基准值是最左端元素6。慢指针i,从左往右;快指针j,从右往左

1

  1. j先走,当遇到比基准值小的元素时停止(5<6);然后i再走,遇到比基准值大的元素时停止(7>6)

2

  1. 如果慢指针没有超过快指针,就将快慢指针所在元素进行交换

3
4
5

  1. 重复以上步骤,直到快慢指针相遇,将快慢指针所在位置元素与基准值进行交换,基准值指针指向快慢指针所在位置

6
7
8

  1. 交换完成后,基准值左边的元素就都小于基准值,基准值右边的元素都大于基准值
  • 以上操作都是相对的,如果pivot选择了最右元素,那么快指针就应该是从左往右遍历的那个
  • 递归地对基准值左右序列进行快排,直到元素全部有序。退出递归的条件——子序列只剩下一个元素,即存在low > high

    同样是上述序列{6,1,2,7,9,3,4,5,10,8},如果慢指针i先走会发生什么?
    (1)pivot=6,i=7>6,j=5<6,交换i与j:{6,1,2,"5",9,3,4,"7",10,8}
    (2)i=9>6,j=4<6,交换i与j:{6,1,2,5,"4",3,"9",10,8}
    (3)i=9=j,交换i/j与pivot:{"9",1,2,5,4,3,"6",10,8},9>6,很明显结果不对。
    结论:如果快指针先走,可以保证快慢指针相遇时元素值小于pivot,交换过来后可以保证pivot左边元素都小于pivot;但是如果慢指针先走,很可能相遇时元素值就大于pivot,交换后pivot左边就会存在比pivot大的元素。

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
public static void quickSort(int[] in, int low, int high) {
//退出递归条件:子序列只有一个元素,此时low = high
if(low > high) return;
int pivot = in[low]; //基准值,选最左边元素
int quick = high; //快指针,比慢指针先走一步,从右往左
int slow = low; //慢指针,从左往右
//当quick遇到了比pivot小的元素,
//同时slow遇到了比pivot大的元素,那么就交换两个元素
while (slow < quick) {
//快指针要先走
//快指针向左,直到找到比pivot小的元素(相等也不行)
//同时要注意,每走一步都要保证快指针没有与慢指针相遇
while (in[quick] >= pivot && slow < quick) {
quick--;
}
//慢指针往右,直到找到比pivot大的元素(相等也不行)
//同时要注意,每走一步都要保证快指针没有与慢指针相遇
while (in[slow] <= pivot && slow < quick) {
slow++;
}
//需要再次判断slow是否已经遇到或超过了quick
if (slow < quick) {
//交换两个元素 —— 可以肯定slow!=quick,是不同元素,
//所以可以用异或交换两个元素
in[slow] = in[slow] ^ in[quick];
in[quick] = in[slow] ^ in[quick];
in[slow] = in[slow] ^ in[quick];
}
}
//将快慢指针所在位置元素与基准值进行交换
//slow与quick相遇的位置,就是基准值指针应该在的位置
in[low] = in[slow];
in[slow] = pivot;
//slow或者quick就是新的pivot,左边元素都比它小,右边元素都比它大
//递归对pivot的左右序列进行快排
quickSort(in, low, slow - 1); //基准值不需要再排序,所以是slow-1
quickSort(in, slow + 1, high); //基准值不需要再排序,所以是slow+1
}

测试:

1
2
3
4
int[] in = {999, 1, 2, 4, 3, -1, 0, 0};
quickSort(in, 0, in.length - 1);
System.out.println(Arrays.toString(in));
//结果为:[-1, 0, 0, 1, 2, 3, 4, 999]

5.1 彩虹排序(NlogK,K是元素种类)

彩虹排序适用于序列中元素种类是已知常数的情况。

  • 彩虹排序(Rainbow Sort)是一种变种的快排,快排是从元素N中选择基准值进行分治,所以时间复杂度是O(NlogN),而彩虹排序则是从元素种类K中选择基准值进行分治,所以时间复杂度是O(NlogK),而K是常数。
  • 具体的分治策略是:递归地从种类K中选择一个基准值,每次使得基准值左边的种类编码小于基准值,右边的种类编码大于基准值
  • 结束递归的条件:
  1. 普通快排的结束递归条件:序列中只有一个元素,low == high(或者low > high
  2. 彩虹排序中额外的结束递归条件:序列中只有一种元素,elementFrom == elementTo(或者elementFrom > elementTo

    elementFromelementTo是指子序列(下标从startend)中元素种类从第elementFrom种到第elementTo种,即元素种类范围

参考LintCode 143. Sort Colors II这题,看看彩虹排序的实际应用:

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
46
/**
* @param colors: A list of integer
* @param k: An integer
* @return: nothing
*/
public static void sortColors2(int[] colors, int k) {
if (colors == null || colors.length == 0) return;
rainbowSort(colors, 0, colors.length - 1, 1, k);
}

//彩虹排序
//@params: colors[] 输入序列,包含从colorFrom到colorTo种类的颜色
//@params: start 子序列开始位置
//@params: end 子序列结束位置
//@params: colorFrom 颜色种类开始位置
//@params: colorTo 颜色种类结束位置
private static void rainbowSort(int[] colors,
int start,
int end,
int colorFrom,
int colorTo) {
//结束递归的条件:
// 1.传统快排结束条件:子序列只有一个元素;
// 2.彩虹排序结束条件:子序列只有一种元素
if (start == end || colorFrom == colorTo) return;
//中间颜色,即基准值pivot
int colorMid = (colorFrom + colorTo) >> 1;
int left = start, right = end;
while (left <= right) {
//找到基准值左边大于基准值的元素
while (left <= right && colors[left] <= colorMid) left++;
//找到基准值右边小于基准值的元素
while (left <= right && colors[right] > colorMid) right--;
//再次判断,如果此时left指针没有超过right指针,就交换两个位置元素
if (left <= right) { //可能相等,不能用异或
int temp = colors[left];
colors[left] = colors[right];
colors[right] = temp;
left++;
right--;
}
}
//由于基准值选择的是中间位置,所以不需要将基准值交换到left所在位置
rainbowSort(colors, start, right, colorFrom, colorMid);
rainbowSort(colors, left, end, colorMid + 1, colorTo); //基准值可以不作为子序列参与下一轮循环
}

测试:

1
2
3
4
5
public static void main(String[] args) {
int[] in = {3,2,2,1,4};
sortColors2(in, 4);
System.out.println(Arrays.toString(in)); //[1,2,2,3,4]
}

6.堆排序(O(N + KlogN),K是排序序列长度)

如果想得到一个序列中第K个最小元素之前的部分序列,最好采用堆排序!!!

  • 堆排序存在非相邻元素之间的交换,所以是非稳定排序
  • 堆的特定:
  1. 堆是一棵完全二叉树。可以用数组表示,节点k有如下特点:父节点为(k-1)/2,左孩子为2k + 1,右孩子为2k + 2
  2. 如果是大根堆,那么对于任何节点,其父节点都会比所有子节点大;如果是小根堆,那么对于任何节点,其父节点都会比所有子节点小

参考上图,理解了下面3个问题,也就理解了堆排序:

  1. 给定一个数组表示的满二叉树,如何构建一个堆?或者说,对一个堆进行了修改后,如何保证修改后的序列仍是一个堆?
  • heapify:对于任意节点来说,堆都有父亲节点大于(或小于)左右儿子的特点,所以,对于任意节点,将其与其左右儿子比较大小,将最大的元素替换到父亲节点,对替换下去的节点重复进行此操作,即可将满二叉树构建成堆。

    比如说上图,对于5-7-8这棵子树来说,5<8,所以将5和8交换位置,然后重新对替换下去的5节点进行heapify

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//heapify:将满二叉树构建为堆
//@param: tree[] 表示堆的数组
//@param: n 节点总数
//@param: i 对哪个节点进行heapify
public static void heapify(int[] tree, int n, int i) {
if(i >= n) return; //结束递归条件:建堆节点下标超过节点总数,i>=n
//根据满二叉树的特点,有:
int left = 2 * i + 1; //左子树
int right = 2 * i + 2; //右子树
//将父亲、左右子树3者中最大的数替换到父亲节点
int max = i;
//注意left 和 right不能越界
if(left < n && tree[left] > tree[max]) max = left;
if (right < n && tree[right] > tree[max]) max = right;
if(max != i) { //如果父亲节点就是最大节点,就不需要重新建堆了
//交换max和i的元素
tree[max] = tree[max] ^ tree[i];
tree[i] = tree[max] ^ tree[i];
tree[max] = tree[max] ^ tree[i];
//对替换下去的节点重新建堆
heapify(tree, n, max);
}
}
  1. 通过步骤1,我们有了将一个修改后的堆还原成堆的能力,那么给定一个数组表示的满二叉树,如何构建出初始的堆?
  • 我们可以从树的倒数第二层(h-1层)逆序地对每个节点进行heapify操作,直到根节点,这样我们就能得到一个初始堆。
  • 为什么不从树的倒数第一层(h层)开始heapify呢?因为倒数第一层没有子节点,本身就是满二叉树,没有heapify的必要
  • 那么如何确定倒数第二层的下标呢?我们知道满二叉树中,k节点的父亲节点是(k-1)/2,我们可以确定倒数第一层的最后一个节点(即数组尾部),该节点的父亲节点正好就位于倒数第二层,这就是我们heapify的起点
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    //初始建堆
    //@params: tree[] 满二叉树
    //@params: n 节点总数
    public static void buildHeap(int[] tree, int n) {
    int last = tree.length;
    int parent = (last - 1) >> 1; //倒数第二层
    for(int i = parent; i >= 0; i--) {
    heapify(tree, n, i);
    }
    }
  1. 现在我们有了一个初始堆,有了能够将更改后的堆构建成新堆的能力,如何进行堆排序?
  • 堆的特点是父亲节点大于(或小于)儿子节点,那么其根节点必定是最大的(最小的),也就是说我们每次构建好堆,都能得到一个剩余元素的最大值(最小值)
  • 将根节点(最大值/最小值)与堆尾元素(也就是数组队尾)进行交换,然后将堆尾剔除并记录下来(当然这是逻辑上的剔除,实际上你可以在heapify的时候不传入堆尾即可),并对剩余元素重新进行heapify。重复此步骤,直到已排序的序列长度满足要求。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    //堆排序
    //@params: tree[] 满二叉树
    //@params: n 节点总数
    public static void heapSort(int[] tree, int n) {
    //构建初始堆
    buildHeap(tree, n);
    //如果只需要k个有序序列,可以提前结束循环
    for(int i = n - 1; i >= 0; i--) {
    //将根节点与堆尾进行交换
    int temp = tree[i];
    tree[i] = tree[0];
    tree[0] = temp;
    //剔除堆尾的最大值,对剩余元素重新进行heapify
    heapify(tree, i, 0);
    }
    }

归并排序 vs 快排 vs 堆排序

  1. 如果从空间复杂度来考虑,首选堆排序,然后是快排,最后是归并排序(需要额外的内存空间)
  2. 如果是从稳定性来考虑,应选择归并排序,因为快排和堆排序并不稳定
  3. 如果从平均情况下的排序速度来考虑,应该选择快排

7.基数排序(O(N*D),D为位数,N为元素个数)

  • 通过对排序的N个元素进行若干趟“分配”与“收集”来实现排序
  • 基数排序(Radix Sort)不需要交换元素位置,所以是稳定性排序
  • 基数排序效率与初始序列是否有序没有关联
  • 在基数排序中,对于任何位数上的基数进行装桶操作时,都需要n + r个临时空间

任何一个阿拉伯数字,它的各个位数上的基数都是以0 ~ 9 来表示的,我们将0 ~ 9视为10个桶。
如:给定序列{50,123,543,187,49,30,0,2,11,100}

  1. 首先根据个位数元素分到指定的桶中。
  2. 将桶中元素按顺序依次弹出,即{50,30,0,100,11,2,123,543,187,49}
  3. 再根据十位数将元素分到指定桶中。
  4. 将桶中元素按顺序依次弹出,即{0,100,2,11,123,30,543,49,50,187}
  5. 再根据百位数将元素分到指定桶中。
  6. 将桶中元素按顺序依次弹出,此时元素就已经有序了
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
46
//基数排序
//不考虑负数的情况
public static int[] radixSort(int[] in) {
int len = in.length;
if (len < 2 || in == null) return in;
//0~9:10个桶,每一个桶是一个不定长的ArrayList
ArrayList<ArrayList<Integer>> buckets = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < 10; i++) buckets.add(new ArrayList<Integer>());
//找出序列中的最大值——不能用排序算法,不然还基数排序个什么劲?
int max = in[0];
for (int i = 1; i < len; i++) max = in[i] > max ? in[i] : max;
//根据最大值,判断位数——即需要循环入桶、出桶的次数
int digit = 0;
while (max != 0) {
max /= 10;
digit++;
}

//入桶 & 出桶
int mod = 10, div = 1;
for (int i = 0; i < digit; i++, mod *= 10, div *= 10) {
//遍历序列,入桶
for (int j = 0; j < len; j++) {
int temp = (in[j] % mod) / div;
//判断对应位的元素,存入桶中
//ArrayList API: T get(int index); & add(T t);
buckets.get(temp).add(in[j]);
}
//遍历所有桶,出桶
int[] newArray = new int[len]; //出桶序列
int cnt = 0;
for (int outArrayIndex = 0; outArrayIndex < buckets.size(); outArrayIndex++) {
for (int inArrayIndex = 0; inArrayIndex < buckets.get(outArrayIndex).size(); inArrayIndex++) {
newArray[cnt++] = buckets.get(outArrayIndex).get(inArrayIndex);
//等价于:
//newArray[cnt] = buckets.get(outArrayIndex).get(inArrayIndex);
//cnt++;
}
//记得出桶后要清空桶,不能影响下一次循环
buckets.get(outArrayIndex).clear();
}
//出桶序列替换原序列
for (int j = 0; j < len; j++) in[j] = newArray[j];
}
return in;
}

8.计数排序

计数排序(Counting Sort)


9.桶排序

桶排序(Bucket Sort)


10.拓扑排序

  • 入度:指向节点的边的个数(比如图中节点1的入度就是0)
  1. 使用BFS进行拓扑排序
  2. 找到图中入度为0的节点,从图中移除
  3. 被移除节点指向的节点,入度减1
  4. 重复2、3
  5. 如果最后不存在入度为0的节点,说明图中有环,这时候拓扑排序无解
-------------本文结束感谢您的阅读-------------

本文标题:算法专题:排序

文章作者:DragonBaby308

发布时间:2019年08月16日 - 20:24

最后更新:2020年02月14日 - 15:22

原始链接:http://www.dragonbaby308.com/Algorithm-sort/

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

急事可以使用右下角的DaoVoice,我绑定了微信会立即回复,否则还是推荐Valine留言喔( ఠൠఠ )ノ
0%