十大排序(JAVA语言)代码 冒泡排序、插入排序、希尔排序、选择排序、快速排序、归并排序、堆排序、桶排序、计数排序、基数排序

发布时间:2024年01月17日

0. 排序算法动画演示地址

https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

1. 冒泡排序

原理简述:从前到后依次比较相邻元素的值,若发现逆序则交换位置,使值较大的元素逐渐从前移向后部。

代码讲解地址:https://www.bilibili.com/video/BV19K411e7dZ/

public class BubbleSort {
    public void swap(int[] array, int index1, int index2){
        array[index1] = array[index1] ^ array[index2];
        array[index2] = array[index1] ^ array[index2];
        array[index1] = array[index1] ^ array[index2];
    }
    public void sortFunction(int[] array){
        for (int i = 0; i < array.length - 1; i++) {
            int count = 0;
            for (int j = 0; j < array.length - i - 1; j++) {
                if(array[j] > array[j + 1]){
                    swap(array, j, j + 1);
                    count++;
                }
            }
            if(count == 0){
                break;
            }
        }
    }
}

2. 插入排序

原理简述:将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。

代码讲解地址:https://www.bilibili.com/video/BV1K5411B7jj

public class InsertSort {
    public void sortFunction(int[] array) {
        int i, j;
        for (i = 1; i < array.length; i++) {
            int temp = array[i];
            for (j = i - 1; j >= 0; j--) {
                if (temp < array[j]) {
                    array[j + 1] = array[j];
                }else {
                    break;
                }
            }
            array[j + 1] = temp;
        }
    }
}

3. 希尔排序

原理简述:先取定一个小于数组长度Array.length 的整数 gap(gap = Array.length / 2)作为第一个增量,把表的全部元素分成 gap 个组,所有相互之间距离为 gap 的倍数的元素放在同一个组中,在各组内进行直接插入排序。然后,减小增量 gap(gap = gap /2),重复上述的分组和排序过程,直至增量减小为 0,即所有元素放在同一组中进行直接插入排序。

代码讲解地址:https://www.bilibili.com/video/BV1Ac411t76T

public class ShellSort {
    public void sortFunction(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            int i, j;
            gap = gap >> 1;
            for (i = 0; i < array.length - gap; i++) {
                int temp = array[i + gap];
                for (j = i; j >= 0; j -= gap) {
                    if (temp < array[j]) {
                        array[j + gap] = array[j];
                    } else {
                        break;
                    }
                }
                array[j + gap] = temp;
            }
        }
    }
}

4. 选择排序

原理简述:从待排序的数据元素中选出最小的一个元素,将其与待排序部分的第一个元素交换位置,然后再从剩余的待排序元素中寻找到最小元素,将其与待排序部分的第一个元素交换位置 。以此类推,直到全部待排序的数据元素的个数为零。

代码讲解地址:https://www.bilibili.com/video/BV125411v7DK

public class SelectSort {
    public void swap(int[] array, int index1, int index2){
        array[index1] = array[index1] ^ array[index2];
        array[index2] = array[index1] ^ array[index2];
        array[index1] = array[index1] ^ array[index2];
    }
    public void sortFunction(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int minNumIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minNumIndex]) {
                    minNumIndex = j;
                }
            }
            if (minNumIndex != i){
                swap(array, minNumIndex, i);
            }
        }
    }
}

5. 快速排序

原理简述:快速排序在每一轮挑选一个基准元素,并让其他比它大的元素移动到数列一边,比它小的元素移动到数列的另一边,从而把数列拆解成了两个部分。

代码讲解地址:https://www.bilibili.com/video/BV12e411e7cF

public class QuickSort {
    public void sortFunction(int[] array, int low, int high) {
        if (low < high) {
            int pivot = array[low];
            int i = low;
            int j = high;
            while (i < j) {
                while ((i < j) && array[j] > pivot) {
                    j--;
                }
                if (i < j) {
                    array[i] = array[j];
                    i++;
                }
                while ((i < j) && array[i] < pivot) {
                    i++;
                }
                if (i < j) {
                    array[j] = array[i];
                    j--;
                }
            }
            array[i] = pivot;
            sortFunction(array, low, i - 1);
            sortFunction(array, i + 1, high);
        }
    }
}

6. 归并排序

原理简述:把长度为n的输入序列分成两个长度为n/2的子序列,对这两个子序列分别采用归并排序,将两个排序好的子序列合并成一个最终的排序序列。

代码讲解地址:https://www.bilibili.com/video/BV1iC4y1Y7Wy

public class MergeSort {
    public void sortFunction(int[] array) {
        int[] tempArray = new int[array.length];
        mergeSortFunction(array, tempArray, 0, array.length - 1);
    }
    public void mergeSortFunction(int[] array, int[] tempArray, int begin, int end) {
        if (begin < end) {
            int mid = begin + ((end - begin) >> 1);
            mergeSortFunction(array, tempArray, begin, mid);
            mergeSortFunction(array, tempArray, mid + 1, end);
            merge(array, tempArray, begin, mid, end);
        }
    }
    public void merge(int[] array, int[] tempArray, int begin, int mid, int end) {
        int leftPos = begin;
        int rightPos = mid + 1;
        int tempArrayPos = begin;
        while (leftPos <= mid && rightPos <= end) {
            if (array[leftPos] < array[rightPos]) {
                tempArray[tempArrayPos++] = array[leftPos++];
            } else {
                tempArray[tempArrayPos++] = array[rightPos++];
            }
        }
        while (leftPos <= mid) {
            tempArray[tempArrayPos++] = array[leftPos++];
        }
        while (rightPos <= end) {
            tempArray[tempArrayPos++] = array[rightPos++];
        }
        for (int i = begin; i <= end; i++) {
            array[i] = tempArray[i];
        }
    }
}

7. 堆排序

原理简述:将待排序的序列构造成一个大顶堆,根据大顶堆的性质,当前堆的根节点(堆顶)就是序列中最大的元素,将堆顶元素和最后一个元素交换,然后将剩下的节点重新构造成一个大顶堆,如此反复,从第一次构建大顶堆开始,每一次构建,我们都能获得一个序列的最大值,然后把它放到大顶堆的尾部。最后,就得到一个有序的序列了。

代码讲解地址:https://www.bilibili.com/video/BV1pa4y117zp

public class HeapSort {
    public void swap(int[] array, int index1, int index2) {
        array[index1] = array[index1] ^ array[index2];
        array[index2] = array[index1] ^ array[index2];
        array[index1] = array[index1] ^ array[index2];
    }
    public void downAdjust(int[] array, int index, int arrayLength) {
        if (index > (arrayLength - 2) >> 1) {
            return;
        } else if ((index * 2) + 2 >= arrayLength) {
            if (array[(index * 2) + 1] > array[index]) {
                swap(array, (index * 2) + 1, index);
            }
        } else {
            if (array[(index * 2) + 2] > array[index] && array[(index * 2) + 2] >= array[(index * 2) + 1]) {
                swap(array, (index * 2) + 2, index);
                downAdjust(array, (index * 2) + 2, arrayLength);
            } else if (array[(index * 2) + 1] > array[index] && array[(index * 2) + 1] > array[(index * 2) + 2]) {
                swap(array, (index * 2) + 1, index);
                downAdjust(array, (index * 2) + 1, arrayLength);
            }
        }
    }
    public void initHeap(int[] array, int arrayLength) {
        boolean hasTwochild = (arrayLength % 2) == 1 ? true : false;
        for (int i = (arrayLength - 2) >> 1; i >= 0; i--) {
            if (hasTwochild) {
                if (array[(i * 2) + 2] > array[i] && array[(i * 2) + 2] >= array[(i * 2) + 1]) {
                    swap(array, (i * 2) + 2, i);
                    downAdjust(array, (i * 2) + 2, arrayLength);
                } else if (array[(i * 2) + 1] > array[i] && array[(i * 2) + 1] > array[(i * 2) + 2]) {
                    swap(array, (i * 2) + 1, i);
                    downAdjust(array, (i * 2) + 1, arrayLength);
                }
            } else {
                if (array[(i * 2) + 1] > array[i]) {
                    swap(array, (i * 2) + 1, i);
                }
                hasTwochild = true;
            }
        }
    }
    public void sortFunction(int[] array) {
        int arrayLength = array.length;
        for (int i = array.length - 1; i > 0; i--) {
            initHeap(array, arrayLength);
            swap(array, i, 0);
            arrayLength--;
        }
    }
}

8. 桶排序

原理简述:将数组元素分到有限数量的桶里。每个桶再个别排序,最后依次把各个桶中的记录列出来记得到有序序列。

代码讲解地址:https://www.bilibili.com/video/BV1ZN4y1v7hQ

public class BucketSort {
    public void sortFunction(int[] array, int bucketNum) {
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int i : array) {
            max = Math.max(max, i);
            min = Math.min(min, i);
        }
        List<List<Integer>> bucketList = new ArrayList<List<Integer>>();
        for (int i = 0; i < bucketNum; i++) {
            bucketList.add(new ArrayList<Integer>());
        }
        for (int i : array) {
            int bucketIndex = (i - min) * (bucketNum - 1) / (max - min);
            List<Integer> list = bucketList.get(bucketIndex);
            list.add(i);
        }
        for (int i = 0, arrIndex = 0; i < bucketList.size(); i++) {
            List<Integer> bucket = bucketList.get(i);
            Collections.sort(bucket);
            for (int num : bucket) {
                array[arrIndex++] = num;
            }
        }

    }
}

9. 计数排序

原理简述:利用数组的索引是有序的,通过将序列中的元素作为索引,其个数作为值放入数组,遍历数组来排序。

代码讲解地址:https://www.bilibili.com/video/BV1ut4y1R7Yk

public class CountSort {
    public void sortFucntion(int[] array) {
        int max = Integer.MIN_VALUE;
        for (int i : array) {
            max = Math.max(max, i);
        }
        int[] numCountArray = new int[max + 1];
        for (int i = 0; i < array.length; i++) {
            numCountArray[array[i]]++;
        }
        int arrayIndex = 0;
        for (int i = 0; i < numCountArray.length; i++) {
            for (int j = 0; j < numCountArray[i]; j++) {
                array[arrayIndex++] = i;
            }
        }
    }
}

10. 基数排序

原理简述:将整数按位数切割成不同的数字,然后按每个位数分别比较。

代码讲解地址:https://www.bilibili.com/video/BV1UT4y187bk

public class RadixSort {
    private void sortFunction(int[] array) {
        int max = Integer.MIN_VALUE;
        for (int i : array) {
            max = Math.max(max, i);
        }
        int maxLength = String.valueOf(max).length();
        LinkedList<Integer>[] radixList = new LinkedList[10];
        for (int i = 0; i < radixList.length; i++) {
            radixList[i] = new LinkedList<Integer>();
        }
        for (int i = 1; i <= maxLength ; i++) {
            for (int j = 0; j < array.length; j++) {
                radixList[getRadix(array[j], i)].add(array[j]);
            }
            int index = 0;
            for (int j = 0; j < radixList.length; j++) {
                while (radixList[j].isEmpty() == false) {
                    array[index++] = radixList[j].remove();
                }
            }
        }
    }
    public int getRadix(int num, int pos) {
        int result = 0;
        for (int i = 1; i <= pos; i++) {
            result = num % 10;
            num /= 10;
        }
        return result;
    }
}

比较(个人电脑测试,仅供参考)

100100010000100000
冒泡排序0ms3ms86ms12962ms
插入排序0ms1ms9ms442ms
希尔排序0ms0ms3ms11ms
选择排序0ms1ms38ms2253ms
快速排序0ms0ms1ms11ms
归并排序0ms0ms2ms10ms
堆排序0ms2ms36ms1986ms
桶排序0ms1ms7ms37ms
计数排序0ms0ms1ms6ms
基数排序0ms1ms5ms34ms
最好时间复杂度最坏时间复杂度平均时间复杂度空间复杂度稳定性
冒泡排序 O ( n ) O(n) O(n) O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1)稳定
插入排序 O ( n ) O(n) O(n) O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1)稳定
希尔排序 O ( n ) O(n) O(n) O ( n 2 ) O(n^2) O(n2) O ( n l o g 2 n ) O(nlog_2n) O(nlog2?n) O ( 1 ) O(1) O(1)不稳定
选择排序 O ( n ) O(n) O(n) O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1)不稳定
快速排序 O ( n l o g 2 n ) O(nlog_2n) O(nlog2?n) O ( n 2 ) O(n^2) O(n2) O ( n l o g 2 n ) O(nlog_2n) O(nlog2?n) O ( l o g 2 n ) O(log_2n) O(log2?n)不稳定
归并排序 O ( n l o g 2 n ) O(nlog_2n) O(nlog2?n) O ( n l o g 2 n ) O(nlog_2n) O(nlog2?n) O ( n l o g 2 n ) O(nlog_2n) O(nlog2?n) O ( n ) O(n) O(n)稳定
堆排序 O ( n ) O(n) O(n) O ( n l o g 2 n ) O(nlog_2n) O(nlog2?n) O ( n l o g 2 n ) O(nlog_2n) O(nlog2?n) O ( 1 ) O(1) O(1)不稳定
桶排序 O ( n + k ) O(n + k) O(n+k) O ( n 2 ) O(n^2) O(n2) O ( n + k ) O(n + k) O(n+k) O ( n + k ) O(n + k) O(n+k)稳定
计数排序 O ( n + k ) O(n + k) O(n+k) O ( n + k ) O(n + k) O(n+k) O ( n + k ) O(n + k) O(n+k) O ( k ) O(k) O(k)稳定
基数排序 O ( n ? k ) O(n * k) O(n?k) O ( n ? k ) O(n * k) O(n?k) O ( n ? k ) O(n * k) O(n?k) O ( n + k ) O(n + k) O(n+k)稳定
文章来源:https://blog.csdn.net/weixin_44144773/article/details/135640176
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。