八大排序算法的java实现

发表于 | 分类于
字数统计: 2,060 | 阅读时长 ≈ 9

每当提到算法，自然少不了各种排序算法，例如冒泡排序，快速排序等等。这篇文章将会介绍用java来实现各种排序算法，一来是自己再巩固一下这一块知识的，二来是将这块知识分享给大家，希望大家和我一起进步。

插入排序

基本思想：
假设有一组个数为n的数，从第二数开始，按照比较规则插入到之前的数中，这样前面两个数就已经是排好序的，然后在从第三个数开始按照同样的规则插入到之前的数中，依次类推直到操作到第n个数。

下面是具体实现源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void insertionSort(int[] arr) {
    int j;
    for(int i = 1; i < arr.length; i++) {
        int tmp = arr[i];
        for(j = i; j > 0; j--) {
            if ( tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
            } else {
                break;
            }
        }
        arr[j] = tmp;
    }
}

希尔排序

基本思想：
算法先将要排序的一组数按某个增量d（n/2,n为要排序数的个数）分成若干组，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。当增量减到1时，进行直接插入排序后，排序完成。

下面是具体实现源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void shellSort(int[] arr) {
    int d1 = arr.length;
    while (true) {
        d1 = (int) Math.ceil(d1 / 2);
        int d = d1;
        for (int x = 0; x < d; x++) {
            for (int i = x + d;i < arr.length;i += d){
                int j = i - d;
                int temp = arr[i];
                for (; j >= 0 && temp < arr[j]; j -= d) {
                    arr[j+d] =arr[j];
                }
                arr[j+d] = temp;
            }
        }
        if (d == 1) {
            break;
        }
    }
}

简单选择排序

基本思想：
在要排序的一组数中，选出最小的一个数与第一个位置的数交换然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

下面是具体实现源码：

1
2
3
4
5
6
7
8
9
10
11
public static void selectSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[i]) {
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
    }
}

堆排序

基本思想：
堆排序是一种树形选择排序，是对直接选择排序的有效改进。
堆的定义如下：
具有n个元素的序列（h1,h2,…,hn),当且仅当满足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1） (i=1,2,…,n/2)时称之为堆。
在这里只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项（大顶堆）。完全二叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储序，使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。

下面是具体实现源码：

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
public class HeapSort {
    public void heapSort(int[] a) {
        int arrayLength = a.length;
        //循环建堆  
        for(int i = 0; i < arrayLength - 1; i++){
            //建堆  
            buildMaxHeap(a, arrayLength - 1 - i);
            //交换堆顶和最后一个元素
            swap(a, 0, arrayLength - 1 - i);
        }
    }
    //交换位置
    private void swap(int[] data, int i, int j) {
        int tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }
    //建堆
    private void buildMaxHeap(int[] data, int lastIndex) {
        //从lastIndex处节点（最后一个节点）的父节点开始
        for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
            //k保存正在判断的节点
            int k = i;
            //如果当前k节点的子节点存在  
            while (k * 2 + 1 <= lastIndex) {
                //k节点的左子节点的索引  
                int biggerIndex = 2 * k + 1;
                //如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在  
                if (biggerIndex < lastIndex) {
                    //若果右子节点的值较大  
                    if (data[biggerIndex] < data[biggerIndex + 1]) {
                        //biggerIndex总是记录较大子节点的索引  
                        biggerIndex++;
                    }
                }
                //如果k节点的值小于其较大的子节点的值  
                if (data[k] < data[biggerIndex]) {
                    //交换他们  
                    swap(data, k, biggerIndex);
                    //将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值  
                    k = biggerIndex;
                } else {
                    break;
                }
            }
        }
    }
}

冒泡排序

基本思想：
假设有一个长度为n的数组，从第一个位置开始，每两个相邻的位置的数值进行比较，如果前面一个位置的数值比后面一个位置的数值大，就交换这两个位置的数值，当最后一对数比较完毕之后，最后一个位置的数值就是最大值。然后我们再以相同的步骤操作数组中除了最后一个位置的所有值，直到没有任何一对数值需要比较。

下面是具体实现源码：

1
2
3
4
5
6
7
8
9
10
11
public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}

快速排序

基本思想：
假设有一个长度为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
public static void fastSort(List<Integer> items) {
    if (items.size() > 1) {
        List<Integer> smaller = new ArrayList<>();
        List<Integer> same = new ArrayList<>();
        List<Integer> larger = new ArrayList<>();
        Integer chosenItem = items.get(items.size() / 2);
        for (Integer item : items) {
            if (item < chosenItem) {
                smaller.add(item);
            } else if (item > chosenItem) {
                larger.add(item);
            } else {
                same.add(item);
            }
        }
        fastSort(smaller);
        fastSort(larger);
        items.clear();
        items.addAll(smaller);
        items.addAll(same);
        items.addAll(larger);
    }
}

归并排序

基本思想：
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

下面是具体实现代码：

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
public class MergeSort {
    public static void sort(int data[], int start, int end) {
        if (start < end) {
            int mid = (start + end) / 2;
            sort(data, start, mid);
            sort(data, mid + 1, end);
            merge(data, start, mid, end);
        }
    }
    public static void merge(int data[], int start, int mid, int end) {
        int temp[] = new int[end - start + 1];
        int i = start;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= end) {
            if (data[i] < data[j]) {
                temp[k++] = data[i++];
            } else {
                temp[k++] = data[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = data[i++];
        }
        while (j <= end) {
            temp[k++] = data[j++];
        }
        for (k = 0, i = start; k < temp.length; k++, i++) {
            data[i] = temp[k];
        }
    }
}

基数排序

基本思想：
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

下面是具体实现代码：

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 class radixSort {
    public void sort(int[] array) {
        //首先确定排序的趟数;
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        int time = 0;
        //判断位数;
        while (max > 0) {
            max /= 10;
            time++;
        }
        //建立10个队列;
        List<ArrayList> queue = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            ArrayList<Integer> queue1 = new ArrayList<>();
            queue.add(queue1);
        }
        //进行time次分配和收集;
        for (int i = 0; i < time; i++) {
            //分配数组元素;
            for (int j = 0; j < array.length; j++) {
                //得到数字的第time+1位数;
                int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
                ArrayList<Integer> queue2 = queue.get(x);
                queue2.add(array[j]);
                queue.set(x, queue2);
            }
            int count = 0;//元素计数器;
            //收集队列元素;
            for (int k = 0; k < 10; k++) {
                while (queue.get(k).size() > 0) {
                    ArrayList<Integer> queue3 = queue.get(k);
                    array[count] = queue3.get(0);
                    queue3.remove(0);
                    count++;
                }
            }
        }
    }
}

小伙伴，如果您觉得文章还不错，欢迎您的支持，我会继续努力创作！