八大排序算法

所谓排序,就是将一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。排序算法,就是如何使得记录按照要求排列的方法。常用的排序算法大致有8种:插入排序(直接插入排序、希尔排序)、选择排序(简单选择排序、堆排序)、交换排序(冒泡排序、快速排序)、归并排序、基数排序。

一、直接插入排序

算法思想:把要排序的数组分为了两个部分,一部分是排序好的元素,另一部分是待插入的元素,如果选择的元素比已排序好的元素小,则交换,直到全部元素都比较过为止。

排序过程:

八大排序算法

代码实现:

public static void main(String[] args) {
    int[] arr = new int[]{10, 5, 12, 13, 7, 4, 2, 15, 9};
    insertSort(arr);
}

public static void insertSort(int[] arr) {
    //第一个元素 默认有序
    for (int i = 1; i < arr.length; i++) {
        //从第二个元素开始
        int temp = arr[i];
        for (int j = i; j >= 0; j--) {
            //若当前元素不是第一个 并且 当前元素大于temp,则向后移动
            if (j > 0 && arr[j - 1] > temp) {
                arr[j] = arr[j - 1];
            } else {
                arr[j] = temp;
                break;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

执行结果:

[5, 10, 12, 13, 7, 4, 2, 15, 9]
[5, 10, 12, 13, 7, 4, 2, 15, 9]
[5, 10, 12, 13, 7, 4, 2, 15, 9]
[5, 7, 10, 12, 13, 4, 2, 15, 9]
[4, 5, 7, 10, 12, 13, 2, 15, 9]  
[2, 4, 5, 7, 10, 12, 13, 15, 9]
[2, 4, 5, 7, 10, 12, 13, 15, 9]
[2, 4, 5, 7, 9, 10, 12, 13, 15]

时间复杂度:最好情况O(n),最坏情况O(n²),平均复杂度O(n²)

空间复杂度:只有temp一个空间,O(1)

二、希尔排序

算法思想:先将整个待排序的序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对所有元素进行直接插入排序。

排序过程:

八大排序算法

代码实现:​​​​​​​

public static void main(String[] args) {
    int[] arr = new int[]{10, 5, 12, 13, 7, 4, 2, 15, 9};
    shellSort(arr);
}

public static void shellSort(int[] arr) {
    //找到步长
    int step = arr.length / 2;
    //步长大于0 当步长等于1时,相当于一次直接插入排序
    while (step > 0) {
        //每个序列都从第二个开始 现在是对每个序列分别进行直接插入排序
        for (int i = step; i < arr.length; i++) {
            //若第i个元素大于i-step元素,直接插入。小于的话,移动有序表后插入 这个if可以省略
            if (arr[i] < arr[i - step]) {
                //上一个元素的位置
                int j = i - step;
                //临时存储当前元素
                int temp = arr[i];
                //元素后移
                arr[i] = arr[i - step];
                //找到元素存储的位置j + step
                while (j >= 0 && arr[j] > temp) {
                    arr[j + step] = arr[j];
                    j = j - step;
                }
                arr[j + step] = temp;
            }
        }
        step = step / 2;
        System.out.println(Arrays.toString(arr));
    }
}

执行结果:​​​​​​​

[7, 4, 2, 13, 9, 5, 12, 15, 10]
[2, 4, 7, 5, 9, 13, 10, 15, 12]
[2, 4, 5, 7, 9, 10, 12, 13, 15]

时间复杂度

最好情况O(nlogn),最坏情况O(n²),平均复杂度O(n^1.5)

空间复杂度:只有temp一个空间,O(1)

三、简单选择排序

算法思想:在要排序的一组数中,选出最小(或者最大)的一个数与第1个位置的数交换;然后在剩下的数当中再找最小(或者最大)的与第2个位置的数交换,依次类推,直到第n-1个元素(倒数第二个数)和第n个元素(最后一个数)比较为止。

排序过程:

八大排序算法

代码实现:​​​​​​​

public static void main(String[] args) {
    int[] arr = new int[]{10, 5, 12, 13, 7, 4, 2, 15, 9};
    selectSort(arr);
}

public static void selectSort(int[] arr) {
    //每次从剩下的元素中选择最小值放到第一个位置
    for (int i = 0; i < arr.length - 1; i++) {
        //记录每一趟最小值坐标
        int min = i;
        //寻找每一趟的最小值 先找到坐标 最后再进行交换 减少交换次数
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        //元素交换
        if (min != i) {
            int temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
        System.out.println(Arrays.toString(arr));
    }
}

执行结果:​​​​​​​

[2, 5, 12, 13, 7, 4, 10, 15, 9]
[2, 4, 12, 13, 7, 5, 10, 15, 9]
[2, 4, 5, 13, 7, 12, 10, 15, 9]
[2, 4, 5, 7, 13, 12, 10, 15, 9]
[2, 4, 5, 7, 9, 12, 10, 15, 13]
[2, 4, 5, 7, 9, 10, 12, 15, 13]
[2, 4, 5, 7, 9, 10, 12, 15, 13]
[2, 4, 5, 7, 9, 10, 12, 13, 15]

时间复杂度最好情况O(n²),最坏情况O(n²),平均复杂度O(n²)

空间复杂度:只有temp一个空间,O(1)

Tips:选择排序可以进行改进,每次不光找到最大值,还可以找到最小值放到最后,从而减少一半的趟数。

四、堆排序

堆的定义如下:n个元素的序列{k1,k2,···,kn},当且仅当满足下关系时,称之为堆:

ki <= k(2i) 或 ki >= k(2i)

ki <= k(2i+1) 或 ki >= k(2i+1)

按照堆的特点可以把堆分为大顶堆小顶堆

大顶堆:每个结点的值都大于或等于其左右孩子结点的值

小顶堆:每个结点的值都小于或等于其左右孩子结点的值

算法思想:

①创建最小堆:将堆所有数据重新排序

②最大堆调整:将堆的末端子节点作调整,使得子节点永远大于父节点

③堆排序:移除位在第一个数据的根节点,并做最小堆调整的递归运算

排序过程:

八大排序算法

八大排序算法

八大排序算法

八大排序算法

代码实现:​​​​​​​

public static void main(String[] args) {
    int[] arr = new int[]{10, 5, 12, 13, 7, 4, 2, 15, 9};
    heapSort(arr);
}

public static void heapSort(int[] arr) {
    //初始堆
    buildHeap(arr, arr.length);
    //从最后一个元素开始对序列进行调整
    System.out.println("堆排序开始");
    for (int i = arr.length - 1; i > 0; i--) {
        //交换堆顶元素arr[0]和堆中最后一个元素
        int temp = arr[i];
        arr[i] = arr[0];
        arr[0] = temp;
        //每次交换堆顶元素和堆中最后一个元素之后,都要对堆顶进行调整
        adjustHeap(arr, 0, i);
    }
    System.out.println("堆排序结束");
}

/**
 * 构建堆
 *
 * @param arr 数组
 * @param len 长度
 */
private static void buildHeap(int[] arr, int len) {
    System.out.println("构建堆开始");
    for (int i = (len - 1) / 2; i >= 0; i--) {
        adjustHeap(arr, i, len);
    }
    System.out.println("构建堆结束");
}

执行结果:​​​​​​​

构建堆开始
[10, 5, 12, 13, 7, 4, 2, 15, 9]
[10, 5, 12, 9, 7, 4, 2, 15, 13]
[10, 5, 2, 9, 7, 4, 12, 15, 13]
[10, 5, 2, 9, 7, 4, 12, 15, 13]
[2, 5, 4, 9, 7, 10, 12, 15, 13]
构建堆结束
堆排序开始
[4, 5, 10, 9, 7, 13, 12, 15, 2]
[5, 7, 10, 9, 15, 13, 12, 4, 2]
[7, 9, 10, 12, 15, 13, 5, 4, 2]
[9, 12, 10, 13, 15, 7, 5, 4, 2]
[10, 12, 15, 13, 9, 7, 5, 4, 2]
[12, 13, 15, 10, 9, 7, 5, 4, 2]
[13, 15, 12, 10, 9, 7, 5, 4, 2]
[15, 13, 12, 10, 9, 7, 5, 4, 2]
堆排序结束

Tips:最小堆输出的是倒序,正序排列可构建最大堆

时间复杂度

最好情况O(nlogn),最坏情况O(nlogn),平均复杂度O(nlogn)

空间复杂度:只有temp一个空间,O(1)

五、冒泡排序

算法思想:在要排序的序列中,对当前还未排好序的全部元素,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒,就好像水泡上浮一样,如果他们的顺序错误就把他们交换过来。

排序过程:

八大排序算法

代码实现:

public static void main(String[] args) {
    int[] arr = new int[]{10, 5, 12, 13, 7, 4, 2, 15, 9};
    bubbleSort(arr);
}
​
public static void bubbleSort(int[] arr) {
    //外层循环控制趟数
    for (int i = arr.length - 1; i > 0; i--) {
        //节点比较 只比较到第i个元素即可
        for (int j = 0; j < i; j++) {
            //交换元素
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

执行结果:

[5, 10, 12, 7, 4, 2, 13, 9, 15]
[5, 10, 7, 4, 2, 12, 9, 13, 15]
[5, 7, 4, 2, 10, 9, 12, 13, 15]
[5, 4, 2, 7, 9, 10, 12, 13, 15]
[4, 2, 5, 7, 9, 10, 12, 13, 15]
[2, 4, 5, 7, 9, 10, 12, 13, 15]
[2, 4, 5, 7, 9, 10, 12, 13, 15]
[2, 4, 5, 7, 9, 10, 12, 13, 15]

时间复杂度最好情况O(n),最坏情况O(n²),平均复杂度O(n²)

空间复杂度:只有temp一个空间,O(1)

Tips:我们可以看到最后几趟都是没有必要的,因此可以在没有元素交换时中止排序,从而减少循环比较时间。

六、快速排序

算法思想:选择一个基准,通过一趟排序将待排元素分为两个部分,其中一部分比基准值都大,另一部分比基准值都小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。(分而治之的思想)

排序过程:

八大排序算法

八大排序算法

此时的基准10找到了自己的位置。然后以此类推,递归的排序左序列和右序列即可使整个序列有序。

代码实现:

public static void main(String[] args) {
    int[] arr = new int[]{10, 5, 12, 13, 7, 4, 2, 15, 9};
    quickSort(arr, 0, arr.length - 1);
}
​
public static void quickSort(int[] arr, int low, int high) {
    //递归的中止条件
    if (arr.length <= 0) {
        return;
    }
    //递归的中止条件
    if (low >= high) {
        return;
    }
    int left = low;
    int right = high;
    //基准 以序列的第一个元素为基准
    int temp = arr[left];
    while (left < right) {
        //从右侧找到比基准小的
        while (left < right && arr[right] >= temp) {
            right--;
        }
        arr[left] = arr[right];
        //从左侧找到比基准大的
        while (left < right && arr[left] <= temp) {
            left++;
        }
        arr[right] = arr[left];
    }
    //放入基准值
    arr[left] = temp;
    System.out.println(Arrays.toString(arr));
    //递归排序左序列
    quickSort(arr, low, left - 1);
    //递归排序右序列
    quickSort(arr, left + 1, high);
}

执行结果:

[9, 5, 2, 4, 7, 10, 13, 15, 12]
[7, 5, 2, 4, 9, 10, 13, 15, 12]
[4, 5, 2, 7, 9, 10, 13, 15, 12]
[2, 4, 5, 7, 9, 10, 13, 15, 12]
[2, 4, 5, 7, 9, 10, 12, 13, 15]

时间复杂度最好情况O(nlogn),最坏情况O(n²),平均复杂度O(nlogn)

空间复杂度:最好情况O(logn),最差情况O(n)

七、归并排序

算法思想:归并排序是将两个(或两个以上)有序序列合并成一个新的有序序列,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

排序过程:

八大排序算法

Tips:图中只是为了方便做了向下移动,实际上没有重新复制一个一模一样的数组。

代码实现:

public static void main(String[] args) {
    int[] arr = new int[]{10, 5, 12, 13, 7, 4, 2, 15, 9};
    mergeSort(arr);
}
​
public static int[] mergeSort(int[] arr) {
    if (arr.length == 1) {
        return arr;
    }
    int mid = arr.length / 2;
    int[] left = Arrays.copyOfRange(arr, 0, mid);
    int[] right = Arrays.copyOfRange(arr, mid, arr.length);
    System.out.println("合并:" + Arrays.toString(left) + "\t" + Arrays.toString(right));
    return merge(mergeSort(left), mergeSort(right));
}
​
/**
 * 合并两个有序数组
 *
 * @param left  数组1
 * @param right 数组2
 * @return 新数组
 */
private static int[] merge(int[] left, int[] right) {
    //合并后的数组大小
    int[] mergeArr = new int[left.length + right.length];
    //i是left坐标,j是right坐标,k是新数组坐标
    int i = 0, j = 0, k = 0;
    //下边是合并两个有序数组  此时传进来的数组left和right一定是有序的
    while (i < left.length && j < right.length) {
        mergeArr[k++] = left[i] <= right[j] ? left[i++] : right[j++];
    }
    //合并left数组剩下的元素
    while (i < left.length) {
        mergeArr[k++] = left[i++];
    }
    //合并right数组剩下的元素
    while (j < right.length) {
        mergeArr[k++] = right[j++];
    }
    System.out.println(Arrays.toString(mergeArr));
    return mergeArr;
}

执行结果:

合并:[10, 5, 12, 13]  [7, 4, 2, 15, 9]
合并:[10, 5]  [12, 13]
合并:[10]  [5]
[5, 10]
合并:[12]  [13]
[12, 13]
[5, 10, 12, 13]
合并:[7, 4]  [2, 15, 9]
合并:[7]  [4]
[4, 7]
合并:[2]  [15, 9]
合并:[15]  [9]
[9, 15]
[2, 9, 15]
[2, 4, 7, 9, 15]
[2, 4, 5, 7, 9, 10, 12, 13, 15]

时间复杂度最好情况O(nlogn),最坏情况O(nlogn),平均复杂度O(nlogn)

空间复杂度:O(n)

八、基数排序

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

排序过程:

八大排序算法

代码实现:

public static void main(String[] args) {
    int[] arr = new int[]{10, 5, 12, 13, 7, 4, 2, 15, 9};
    radixSort(arr);
}
​
public static void radixSort(int[] arr) {
    if (arr.length == 1) {
        return;
    }
    //找到数组中的最大值
    int max = 0;
    for (int item : arr) {
        if (max < item) {
            max = item;
        }
    }
    //获取最大位数
    int maxDigit = 1;
    while (max / 10 > 0) {
        maxDigit++;
        max = max / 10;
    }
    //申请桶空间
    int[][] buckets = new int[10][arr.length];
    int divisor = 10;
    for (int i = 0; i < maxDigit; i++) {
        //只有10个数字 key是每个位置的值 value存放该值的个数
        int[] bucketLength = new int[10];
        //分配:将所有元素分配到桶中
        for (int value : arr) {
            int whereBucket = (value % divisor) / (divisor / 10);
            buckets[whereBucket][bucketLength[whereBucket]] = value;
            //该位的个数
            bucketLength[whereBucket]++;
        }
        //收集:将不同桶里数据拿出来
        int k = 0;
        for (int j = 0; j < buckets.length; j++) {
            for (int l = 0; l < bucketLength[j]; l++) {
                arr[k++] = buckets[j][l];
            }
        }
        System.out.println(Arrays.toString(arr));
        divisor = divisor * 10;
    }
}

执行结果:

[10, 12, 2, 13, 4, 5, 15, 7, 9]
[2, 4, 5, 7, 9, 10, 12, 13, 15]

时间复杂度d:位数,r:基数,n:序列个数

最好情况O(d*(n+r)),最坏情况O(d*(n+r)),平均复杂度O(d*(n+r))

空间复杂度:O(n+r)

 今天的分享就到此结束啦,喜欢的小伙伴记得点赞呦。

关注公众号JavaGrowUp,下期不迷路,获取更多精彩内容。

八大排序算法

上一篇:Linux系统安装Redis超级详细保姆及教程


下一篇:LLVM 源码下载及编译