本文共 6761 字，大约阅读时间需要 22 分钟。

最近正好想复习一下数据结构与算法，于是手撸了一下基本的排序算法，代码注释都比较全，就不做过多解释了

1. 插入排序（直接插入、希尔排序、二分插入）
2. 选择排序（直接选择、堆排序）
3. 交换排序（冒泡排序、快速排序）
4. 归并排序

 1、直接插入

import java.util.Arrays;/** * @Author: wuyaohua * @Description: * @Date: Created in 13:03 2018-08-20 */public class DirectInsertSorting {    /**     *  description：直接插入法     * 重点：每次都是往一个已排好顺序的数组中插     * 时间复杂度：平均O(n^2),最好O(n),最差O(n^2)  稳定、简单  空间福再度O（1）     * 适用于n数据量大，无序     */    private static void directInsertSort(int[] a){        for(int i = 0 ; i < a.length ; i++){            int j ;            int temp = a[i];            for ( j = i-1 ; j >= 0 ; j--){                // 如果a[j]比temp大，则a[j]的数后移一位                if(temp < a[j]){                    a[j+1] = a[j];                }else{                    break;                }            }            a[j+1] = temp;        }    }    public static void main(String[] args) {        int[] a = {1,5,6,2,6,2,1,6,8,3,5};        System.out.println(Arrays.toString(a));        DirectInsertSorting.directInsertSort(a);        System.out.println(Arrays.toString(a));    }}

2、二分插入

import java.util.Arrays;/** * @Author: wuyaohua * @Description: * @Date: Created in 14:00 2018-08-20 */public class BinaryInsertSorting {    /**     * decription：二分插入法     * 重点：跟直接插入一样，针对向一个有序数组里插入，每次直接跟中间值比较     * 时间复杂度：     */    private static void binaryInsetSort(int[] a){        for(int i = 0 ; i < a.length ; i++){            int temp = a[i];            int left = 0;            int mid = 0;            int right = i-1;            while(left <= right){                mid = (left + right)/2;                if(a[mid] > temp){                    right = mid -1 ;                }else {                    left = mid + 1;                }            }            for( int j = i -1 ; j >= left ; j-- ){                a[j+1] = a[j];            }            if(left !=  i){                a[left] = temp;            }        }    }    public static void main(String[] args) {        int[] a = {1,5,6,2,6,2,1,6,8,3,5};        System.out.println(Arrays.toString(a));        BinaryInsertSorting.binaryInsetSort(a);        System.out.println(Arrays.toString(a));    }}

3、希尔排序

import java.util.Arrays;/** * @Author: wuyaohua * @Description: * @Date: Created in 16:19 2018-08-20 */public class ShellInsertSorting {    /**     * @Description:希尔排毒     * 重点：设定一个gap（增量值），将距离为gap的放在一组，进行内部排序，直到gap为1转化为直接插入，但是宏观上已经是有序的了     *       所以移动数据的次数会比直接插入少很多     * 时间复杂度：O(n^3/2),跟设定的增量值有关，不稳定     * 空间福再度O（1）     */    private static void shellInsertSort(int[] a){        for(int gap = a.length/2 ; gap > 0 ; gap = gap/2){            for(int i = gap ; i < a.length ; i++){                int j = i;                //从第gap个位置开始，逐个跟前面的距离gap的值进行交换排序                while(j-gap>0 && a[j]

4、直接选择

import java.util.Arrays;/** * @Author: wuyaohua * @Description: * @Date: Created in 16:49 2018-08-20 */public class DirectSelectSorting {    private static void directSelectSort(int[] a){        for( int i = 0 ; i < a.length ; i ++){            //存放最小值            int min = a[i];            //存放最小数索引            int n = i;            for(int j = i + 1 ; j < a.length ; j++){                //如果a[j]比min小，则将值赋值给min，同时把索引给n                if(a[j]

5、堆排序（较复杂）

import java.util.Arrays;/** * @Author: wuyaohua * @Description: * @Date: Created in 17:42 2018-08-20 */public class HeapSorting {    /**    * 交换数组元素    */    private static void swap(int[] a, int i ,int j){        a[i] = a[i] + a[j];        a[j] = a[i] - a[j];        a[i] = a[i] - a[j];    }    /**     * 调整大顶堆，找到最大值     */    private static void adjustHeap(int[] a,int start, int length){        //存储当前父节点树的值        int temp = a[start];        //先从左子树开始        for(int i = 2*start + 1; i <  length ; i = 2*i+1){            //如果右节点值比左节点值大，则直接把右节点跟父节点比            if(i+1
   
    a[i]){                i++;            }            if(a[i]>temp) {                //直接赋值就可以了,同时记录节点索引                a[start] = a[i];                start = i ;            }else{                //两个子节点都比父节点小，就直接退出                break;            }        }        //结束后，把原来得值付给最后一次赋值的节点        a[start] = temp;    }    /**      * @Author : wuyaohua      * @Date : 2018-08-20  18:24      * @Description :堆排序      * @Param : [a]      * @Return : void      * 首先构建一个大顶堆，然后每次讲堆顶元素和最后一个交换位置，再重新对n-1个重新建堆      * 时间复杂度O(nlog2n)，空间复杂度O(1)，不稳定    */    private static void heapSort(int[] a){        //构建大顶堆        for(int i = a.length/2 -1 ; i>= 0;i--){            adjustHeap(a,i,a.length);        }        //交换堆顶和最后一个节点值        for(int i = a.length-1 ; i>0 ; i--){            swap(a,0,i);            //重建大顶堆            adjustHeap(a,0,i);        }    }    public static void main(String[] args) {        int[] a = {1,5,6,2,6,2,1,6,8,3,5};        System.out.println(Arrays.toString(a));        HeapSorting.heapSort(a);        System.out.println(Arrays.toString(a));    }}
   

6、冒泡排序

import java.util.Arrays;/** * @Author: wuyaohua * @Description: * @Date: Created in 9:45 2018-08-21 */public class BubbleSorting {    /**      * @Author : wuyaohua      * @Date : 2018-08-21  9:52      * @Description : 冒泡排序，每比较一个循环，最大的数就会到最后面，时间复杂度O(n^2),空间复杂度O(1)，稳定      * @Param : [a]      * @Return : void    */    private static void bubbleSort(int[] a){        for(int i = 0; i < a.length-1 ; i ++){            for(int j = 0 ; j < a.length -i -1  ; j++){                if(a[j]>a[j+1]) {swap(a,j,j+1);}            }        }    }    /**     * 交换数组元素     */    private static void swap(int[] a, int i ,int j){        a[i] = a[i] + a[j];        a[j] = a[i] - a[j];        a[i] = a[i] - a[j];    }    public static void main(String[] args) {        int[] a = {1,5,6,2,6,2,1,6,8,3,5};        System.out.println(Arrays.toString(a));        BubbleSorting.bubbleSort(a);        System.out.println(Arrays.toString(a));    }}

7、快速排序

import java.util.Arrays;/** * @Author: wuyaohua * @Description: * @Date: Created in 10:03 2018-08-21 */public class QuickSorting {    private static void quick(int a[]){        if(a.length>0){            quickSort(a,0,a.length-1);        }    }    /**      * @Author : wuyaohua      * @Date : 2018-08-21  10:25      * @Description : 快速排序，每次选一个基准数，把比基准大的方右边，基准小的放左边，再递归执行      *                 时间复杂度（O(nlogn)），空间复杂度（O（nlogn），不稳定      * @Param : [a, low, high]      * @Return : void    */    private static void quickSort(int[] a,int low, int high){        //递归快排，必须要有这个条件，否则容易导致堆栈溢出异常        if(low
   
    =temp){                high--;            }            a[low] = a[high];            //然后从左边开始，找到比基准大的数，赋值到之前high的位置，因为high的值已经赋给a[low]了            while(low
   

8、归并排序

import java.util.Arrays;/** * @Author: wuyaohua * @Description: * @Date: Created in 10:39 2018-08-21 */public class MergeSorting {    private static void sort(int[] a,int low ,int high){        int middle = (low+high)/2;        if(low

转载地址：https://blog.csdn.net/JohneyWu/article/details/81916681 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！