Fork me on GitHub

数据结构-排序

冒泡排序

重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序出现错误就把他们交换过来.走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成.

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”.

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
public class BubbleSort {

private BubbleSort() {
}

public static void sort(int[] arr) {

int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
for (int val :arr){
System.out.print(val+ "\t");
}
System.out.println();
}
System.out.println("------------------------------");
}
}


private static void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}

public static void main(String[] args) {

int[] arr = {9, 5, 8, 7, 2, 4, 11, 6, 14, 3};
BubbleSort.sort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]);
System.out.print(' ');
}
System.out.println();
}
}

过程如下:
每次排序将最大值放到最后

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
47
48
49
50
51
52
53
54
55
5	9	8	7	2	4	11	6	14	3	
5 8 9 7 2 4 11 6 14 3
5 8 7 9 2 4 11 6 14 3
5 8 7 2 9 4 11 6 14 3
5 8 7 2 4 9 11 6 14 3
5 8 7 2 4 9 11 6 14 3
5 8 7 2 4 9 6 11 14 3
5 8 7 2 4 9 6 11 14 3
5 8 7 2 4 9 6 11 3 14
------------------------------
5 8 7 2 4 9 6 11 3 14
5 7 8 2 4 9 6 11 3 14
5 7 2 8 4 9 6 11 3 14
5 7 2 4 8 9 6 11 3 14
5 7 2 4 8 9 6 11 3 14
5 7 2 4 8 6 9 11 3 14
5 7 2 4 8 6 9 11 3 14
5 7 2 4 8 6 9 3 11 14
------------------------------
5 7 2 4 8 6 9 3 11 14
5 2 7 4 8 6 9 3 11 14
5 2 4 7 8 6 9 3 11 14
5 2 4 7 8 6 9 3 11 14
5 2 4 7 6 8 9 3 11 14
5 2 4 7 6 8 9 3 11 14
5 2 4 7 6 8 3 9 11 14
------------------------------
2 5 4 7 6 8 3 9 11 14
2 4 5 7 6 8 3 9 11 14
2 4 5 7 6 8 3 9 11 14
2 4 5 6 7 8 3 9 11 14
2 4 5 6 7 8 3 9 11 14
2 4 5 6 7 3 8 9 11 14
------------------------------
2 4 5 6 7 3 8 9 11 14
2 4 5 6 7 3 8 9 11 14
2 4 5 6 7 3 8 9 11 14
2 4 5 6 7 3 8 9 11 14
2 4 5 6 3 7 8 9 11 14
------------------------------
2 4 5 6 3 7 8 9 11 14
2 4 5 6 3 7 8 9 11 14
2 4 5 6 3 7 8 9 11 14
2 4 5 3 6 7 8 9 11 14
------------------------------
2 4 5 3 6 7 8 9 11 14
2 4 5 3 6 7 8 9 11 14
2 4 3 5 6 7 8 9 11 14
------------------------------
2 4 3 5 6 7 8 9 11 14
2 3 4 5 6 7 8 9 11 14
------------------------------
2 3 4 5 6 7 8 9 11 14
------------------------------
2 3 4 5 6 7 8 9 11 14

将算法进行修改, 使其支持自定义类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    public static void sort(Comparable[] arr) {

int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j].compareTo(arr[j + 1]) > 0) {
swap(arr, j, j + 1);
}
// for (int val :arr){
// System.out.print(val+ "\t");
// }
// System.out.println();
}
// System.out.println("------------------------------");
}
}


private static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}

创建一个学生类进行测试

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
public class Student implements Comparable<Student> {

private String name;
private int score;

public Student(String name, int score){
this.name = name;
this.score = score;
}

// 定义Student的compareTo函数
// 如果分数相等,则按照名字的字母序排序
// 如果分数不等,则分数高的靠前
@Override
public int compareTo(Student that) {

if( this.score < that.score )
return -1;
else if( this.score > that.score )
return 1;
else // this.score == that.score
return this.name.compareTo(that.name);
}

// 定义Student实例的打印输出方式
@Override
public String toString() {
return "Student: " + this.name + " " + Integer.toString( this.score );
}
}

进行测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
        // 测试自定义的类 Student
Student[] d = new Student[4];
d[0] = new Student("D", 90);
d[1] = new Student("C", 100);
d[2] = new Student("B", 95);
d[3] = new Student("A", 95);
SelectionSort.sort(d);
for (int i = 0; i < d.length; i++)
System.out.println(d[i]);


Student: D 90
Student: A 95
Student: B 95
Student: C 100

对冒泡排序进行优化,使它效率更高一些:添加一个标记,如果一趟遍历中发生了交换,则标记为true,否则为false.如果某一趟没有发生交换,说明排序已经完成!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
    public static void sort(Comparable[] arr) {

int n = arr.length;
int flag;
for (int i = 0; i < n - 1; i++) {
flag = 0;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j].compareTo(arr[j + 1]) > 0) {
swap(arr, j, j + 1);
flag = 1;
}
// for (int val :arr){
// System.out.print(val+ "\t");
// }
// System.out.println();
}
// System.out.println("------------------------------");
if (flag == 0)
break;
}
}

选择排序

选择排序(Selection sort)是一种简单直观的排序算法.它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾.以此类推,直到全部待排序的数据元素排完. 选择排序是不稳定的排序方法.

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
public class SelectionSort {

private SelectionSort() {
}

public static void sort(int[] arr) {

int n = arr.length;
for (int i = 0; i < n; i++) {
// 寻找[i, n)区间里的最小值的索引
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex])
minIndex = j;
}
swap(arr, i, minIndex);

for (int val :arr){
System.out.print(val+ "\t");
}
System.out.println();
}
}

private static void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}

public static void main(String[] args) {

int[] arr = {9, 5, 8, 7, 2, 4, 11, 6, 14, 3};
SelectionSort.sort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+"\t");
}
System.out.println();
}
}
1
2
3
4
5
6
7
8
9
10
11
2	5	8	7	9	4	11	6	14	3	
2 3 8 7 9 4 11 6 14 5
2 3 4 7 9 8 11 6 14 5
2 3 4 5 9 8 11 6 14 7
2 3 4 5 6 8 11 9 14 7
2 3 4 5 6 7 11 9 14 8
2 3 4 5 6 7 8 9 14 11
2 3 4 5 6 7 8 9 14 11
2 3 4 5 6 7 8 9 11 14
2 3 4 5 6 7 8 9 11 14
2 3 4 5 6 7 8 9 11 14

构建一个生成测试数据的方法

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import java.lang.reflect.Method;

public class SortTestHelper {

// SortTestHelper不允许产生任何实例
private SortTestHelper() {
}

// 生成有n个元素的随机数组,每个元素的随机范围为[rangeL, rangeR]
public static Integer[] generateRandomArray(int n, int rangeL, int rangeR) {

assert rangeL <= rangeR;

Integer[] arr = new Integer[n];

for (int i = 0; i < n; i++)
arr[i] = new Integer((int) (Math.random() * (rangeR - rangeL + 1) + rangeL));
return arr;
}

// 打印arr数组的所有内容
public static void printArray(Object arr[]) {

for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]);
System.out.print(' ');
}
System.out.println();

return;
}

// 判断arr数组是否有序
public static boolean isSorted(Comparable[] arr) {

for (int i = 0; i < arr.length - 1; i++)
if (arr[i].compareTo(arr[i + 1]) > 0)
return false;
return true;
}

// 测试sortClassName所对应的排序算法排序arr数组所得到结果的正确性和算法运行时间
public static void testSort(String sortClassName, Comparable[] arr) {

try {
// 通过sortClassName获得排序函数的Class对象
Class sortClass = Class.forName(sortClassName);
// 通过排序函数的Class对象获得排序方法
Method sortMethod = sortClass.getMethod("sort", new Class[]{Comparable[].class});
// 排序参数只有一个,是可比较数组arr
Object[] params = new Object[]{arr};

long startTime = System.nanoTime();
// 调用排序函数
sortMethod.invoke(null, params);
long endTime = System.nanoTime();

assert isSorted(arr);

System.out.println(sortClass.getSimpleName() + " : " + (endTime - startTime)/1e9 + "s");
} catch (Exception e) {
e.printStackTrace();
}
}
}

简单测试

1
2
3
4
5
6
7
8
9
10
11
    public static void main(String[] args) {

// 测试排序算法辅助函数
int N = 100000;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
SortTestHelper.testSort("SelectionSort", arr);

return;
}

SelectionSort : 13.9119643s

插入排序

把n个待排序的元素看成为一个有序表和一个无序表.开始时有序表中只包含1个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,将它插入到有序表中的适当位置,使之成为新的有序表,重复n-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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class InsertionSort {

// 我们的算法类不允许产生任何实例
private InsertionSort() {
}

public static void sort(Comparable[] arr) {

int n = arr.length;
for (int i = 0; i < n; i++) {

// 寻找元素arr[i]合适的插入位置


for (int j = i; j > 0; j--)
if (arr[j].compareTo(arr[j - 1]) < 0)
swap(arr, j, j - 1);
else
break;


}
}

private static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}

// 测试InsertionSort
public static void main(String[] args) {

int N = 20000;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
SortTestHelper.testSort("InsertionSort", arr);

return;
}
}

归并排序

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并.

根据具体的实现,归并排序包括”从上往下”和”从下往上”2种方式.

  1. 从下往上的归并排序:将待排序的数列分成若干个长度为1的子数列,然后将这些数列两两合并;得到若干个长度为2的有序数列,再将这些数列两两合并;得到若干个长度为4的有序数列,再将它们两两合并;直接合并成一个数列为止.这样就得到了我们想要的排序结果.(参考下面的图片)

  2. 从上往下的归并排序:它与”从下往上”在排序上是反方向的.它基本包括3步:
    ① 分解 – 将当前区间一分为二,即求分裂点mid = (low + high)/2;
    ② 求解 – 递归地对两个子区间a[low...mid]a[mid+1...high]进行归并排序.递归的终结条件是子区间长度为1.
    ③ 合并 – 将已排序的两个子区间a[low...mid]a[mid+1...high]归并为一个有序的区间a[low...high].

自顶向下

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
// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
private static void merge(Comparable[] arr, int l, int mid, int r) {

Comparable[] aux = Arrays.copyOfRange(arr, l, r+1);

// 初始化,i指向左半部分的起始索引位置l;j指向右半部分起始索引位置mid+1
int i = l, j = mid+1;
for( int k = l ; k <= r; k ++ ){

if( i > mid ){ // 如果左半部分元素已经全部处理完毕
arr[k] = aux[j-l]; j ++;
}
else if( j > r ){ // 如果右半部分元素已经全部处理完毕
arr[k] = aux[i-l]; i ++;
}
else if( aux[i-l].compareTo(aux[j-l]) < 0 ){ // 左半部分所指元素 < 右半部分所指元素
arr[k] = aux[i-l]; i ++;
}
else{ // 左半部分所指元素 >= 右半部分所指元素
arr[k] = aux[j-l]; j ++;
}
}
}

// 递归使用归并排序,对arr[l...r]的范围进行排序
private static void sort(Comparable[] arr, int l, int r) {

if (l >= r)
return;

int mid = (l+r)/2;

sort(arr, l, mid);
sort(arr, mid + 1, r);

merge(arr, l, mid, r);
}

public static void sort(Comparable[] arr){

int n = arr.length;
sort(arr, 0, n-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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
    // 将arr[l...mid]和arr[mid+1...r]两部分进行归并
private static void merge(Comparable[] arr, int l, int mid, int r) {

Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1);

// 初始化,i指向左半部分的起始索引位置l;j指向右半部分起始索引位置mid+1
int i = l, j = mid + 1;
for (int k = l; k <= r; k++) {

if (i > mid) { // 如果左半部分元素已经全部处理完毕
arr[k] = aux[j - l];
j++;
} else if (j > r) { // 如果右半部分元素已经全部处理完毕
arr[k] = aux[i - l];
i++;
} else if (aux[i - l].compareTo(aux[j - l]) < 0) { // 左半部分所指元素 < 右半部分所指元素
arr[k] = aux[i - l];
i++;
} else { // 左半部分所指元素 >= 右半部分所指元素
arr[k] = aux[j - l];
j++;
}
}
}

public static void sort(Comparable[] arr) {

int n = arr.length;

// Merge Sort Bottom Up 无优化版本
// for (int sz = 1; sz < n; sz *= 2)
// for (int i = 0; i < n - sz; i += sz+sz)
// // 对 arr[i...i+sz-1] 和 arr[i+sz...i+2*sz-1] 进行归并
// merge(arr, i, i+sz-1, Math.min(i+sz+sz-1,n-1));

// Merge Sort Bottom Up 优化
// 对于小数组, 使用插入排序优化
for (int i = 0; i < n; i += 16)
InsertionSort.sort(arr, i, Math.min(i + 15, n - 1));

// 外循环表示每次合并多少个元素
// 内循环表示每个合并区间的起始位置
for (int sz = 16; sz < n; sz += sz)
for (int i = 0; i < n - sz; i += sz + sz)
// 对于arr[mid] <= arr[mid+1]的情况,不进行merge
// Math.min(i + sz + sz - 1, n - 1), 防止越界,
if (arr[i + sz - 1].compareTo(arr[i + sz]) > 0)
merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, n - 1));

}

快速排序

快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为较小和较大的2个子序列,然后递归地排序两个子序列.

步骤为:

  1. 挑选基准值:从数列中挑出一个元素,称为“基准”(pivot),
  2. 分割:重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(与基准值相等的数可以到任何一边).在这个分割结束之后,对基准值的排序就已经完成,
  3. 递归排序子序列:递归地将小于基准值元素的子序列和大于基准值元素的子序列排序.

递归到最底部的判断条件是数列的大小是零或一,此时该数列显然已经有序.

选取基准值有数种具体方法,此选取方法对排序的时间性能有决定性影响.

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
// 对arr[l...r]部分进行partition操作
// 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
// 返回选中的基准
private static int partition(Comparable[] arr, int l, int r){

Comparable v = arr[l];

int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v
for( int i = l + 1 ; i <= r ; i ++ )
if( arr[i].compareTo(v) < 0 ){
j ++;
swap(arr, j, i);
}

swap(arr, l, j);

return j;
}

// 递归使用快速排序,对arr[l...r]的范围进行排序
private static void sort(Comparable[] arr, int l, int r){

if( l >= r )
return;

int p = partition(arr, l, r);
sort(arr, l, p-1 );
sort(arr, p+1, r);
}

public static void sort(Comparable[] arr){

int n = arr.length;
sort(arr, 0, n-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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

// 不使用一个额外的最大堆, 直接在原数组上进行原地的堆排序
public class HeapSort3 {
// 我们的算法类不允许产生任何实例
private HeapSort3(){}

public static void sort(Comparable[] arr){

int n = arr.length;

// 注意,此时我们的堆是从0开始索引的
// 从(最后一个元素的索引-1)/2开始
// 最后一个元素的索引 = n-1
for( int i = (n-1-1)/2 ; i >= 0 ; i -- )
shiftDown2(arr, n, i);

for( int i = n-1; i > 0 ; i-- ){
swap( arr, 0, i);
shiftDown2(arr, i, 0);
}
}

// 交换堆中索引为i和j的两个元素
private static void swap(Object[] arr, int i, int j){
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}

// 原始的shiftDown过程
private static void shiftDown(Comparable[] arr, int n, int k){

while( 2*k+1 < n ){
int j = 2*k+1;
if( j+1 < n && arr[j+1].compareTo(arr[j]) > 0 )
j += 1;

if( arr[k].compareTo(arr[j]) >= 0 )break;

swap( arr, k, j);
k = j;
}
}

// 优化的shiftDown过程, 使用赋值的方式取代不断的swap,
private static void shiftDown2(Comparable[] arr, int n, int k){

Comparable e = arr[k];
while( 2*k+1 < n ){
int j = 2*k+1;
if( j+1 < n && arr[j+1].compareTo(arr[j]) > 0 )
j += 1;

if( e.compareTo(arr[j]) >= 0 )
break;

arr[k] = arr[j];
k = j;
}

arr[k] = e;
}

// 测试 HeapSort
public static void main(String[] args) {

int N = 1000000;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
SortTestHelper.testSort("HeapSort3", arr);

return;
}
}

索引堆

上面的堆是通过改变元素位置来进行的, 可是由于数组中元素位置的改变,我们将面临着几个局限性.

  1. 如果我们的元素是十分复杂的话,比如像每个位置上存的是一篇10万字的文章.那么交换它们之间的位置将产生大量的时间消耗.

  2. 由于我们的数组元素的位置在构建成堆之后发生了改变,那么我们之后就很难索引到它,很难去改变它.例如我们在构建成堆后,想去改变一个原来元素的优先级(值),将会变得非常困难.

可能我们在每一个元素上再加上一个属性来表示原来位置可以解决,但是这样的话,我们必须将这个数组遍历一下才能解决.(性能低效)

针对以上问题,我们就需要引入索引堆(Index Heap)的概念.

对于索引堆来说,我们将数据和索引这两部分分开存储.真正表征堆的这个数组是由索引这个数组构建成的.

索引堆

而在构建堆(以最大索引堆为例)的时候,比较的是data中的值(即原来数组中对应索引所存的值),构建成堆的却是index域

而构建完之后,data域并没有发生改变,位置改变的是index域.

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
// 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引
private void shiftUp(int k){

while( k > 1 && data[indexes[k/2]].compareTo(data[indexes[k]]) < 0 ){
swapIndexes(k, k/2);
k /= 2;
}
}

// 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引
private void shiftDown(int k){

while( 2*k <= count ){
int j = 2*k;
if( j+1 <= count && data[indexes[j+1]].compareTo(data[indexes[j]]) > 0 )
j ++;

if( data[indexes[k]].compareTo(data[indexes[j]]) >= 0 )
break;

swapIndexes(k, j);
k = j;
}
}

// 交换索引堆中的索引i和j
// 由于有了反向索引reverse数组,
// indexes数组发生改变以后, 相应的就需要维护reverse数组
private void swapIndexes(int i, int j){
int t = indexes[i];
indexes[i] = indexes[j];
indexes[j] = t;

reverse[indexes[i]] = i;
reverse[indexes[j]] = j;
}

http://www.imooc.com/article/37045

算法稳定性

https://www.cnblogs.com/xinaixia/p/4444576.html

-------------本文结束感谢您的阅读-------------
坚持原创技术分享,您的支持将鼓励我继续创作!
0%