首页

常用的排序算法

  1. 冒泡排序
/**
 * 冒泡排序
 * 时间复杂度：O(n*n)
 * 空间复杂度：O(1)
 * 稳定性：稳定
 * 描述：通过与相邻的元素比较交换来把最小的元素交换到前面
 */
public class BubbleSort {

    /**
     * @param nums
     */
    public static void bubbleSort(int[] nums){
        // 最后一轮不用再比较
        for (int i=0;i<nums.length-1;i++){
            // 一轮过后最大的元素到了最后面
            for (int j=0;j<nums.length-1-i;j++){
                if (nums[j]>nums[j+1]){
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                }
            }
        }
    }
    /**
     * 另一种写法
     * 依次从数组中取一个数据，用这个数据和它之后的数据相比较
     * @param nums
     */
    public static void bubbleSort2(int[] nums){
        for (int i=0;i<nums.length-1;i++){
            // 一轮过后小的元素到最前面
            for (int j=i+1;j<nums.length;j++){
                if (nums[i]>nums[j]){
                    int temp = nums[j];
                    nums[j] = nums[i];
                    nums[i] = temp;
                }
            }
        }
    }
}
  1. 直接插入排序
/**
 * 插入排序
 * 时间复杂度：O(n*n)
 * 空间复杂度：O(1)
 * 稳定性：稳定
 * 描述：对未排序数据，在已排序数据中从后向前扫描，找到相应位置并插入
 */
public class InsertionSort {
    public static void insertionSort(int[] nums) {
        int len = nums.length;
        // 从第二个数开始
        for (int i = 1; i < len; i++) {
            // 选定一个元素
            int key = nums[i];
            // 扫描起始位置为已排序序列的末尾处
            int j = i - 1;
            // 扫描已排序序列，若元素比key大则将元素向后移
            while (j >= 0 && nums[j] > key) {
                nums[j + 1] = nums[j];
                j--;
            }
            // 将选定的元素插入到查找到的位置
            nums[j + 1] = key;
        }
    }
}
  1. 归并排序
/**
 * 归并排序
 * 时间复杂度：O(nlog2n)
 * 空间复杂度：o(n)
 * 稳定性：稳定
 * 描述：分治法的思想，
 * 先使每个子序列有序,再将已有序的子序列合并，
 * 最后得到完全有序的序列；
 */
public class MergeSort {
    public static void mergeSort(int[] nums){
        sort(nums,0,nums.length-1);
    }
    // 分别对左右排序
    public static void sort(int[] nums,int low,int high){
        if (low==high){
            return;
        }
        int mid = low + ( high - low ) / 2;
        // 对左边排序
        sort(nums,low,mid);
        // 对右边排序
        sort(nums,mid+1,high);
        // 合并有序数组
        merge(nums,low,mid,high);

    }
    // 合并
    public static void merge(int[] nums,int low,int mid,int high){
        // 暂时保存数组
        int[] temp = new int[high-low+1];
        int i = 0;
        int l = low;
        int m = mid+1;
        // 从有序数组中挑选最小的放入temp中
        while (l<=mid&&m<=high){
            temp[i++] = nums[l]<nums[m]?nums[l++]:nums[m++];
        }
        // 处理未被放入的元素
        while (l<=mid){
            temp[i++] = nums[l++];
        }
        while (m<=high){
            temp[i++] = nums[m++];
        }
        // 将排序后的序列放回原序列
        System.arraycopy(temp,0,nums,low,temp.length);
    }
}
  1. 选择排序
/**
 * 选择排序
 * 时间复杂度：O(n*n)
 * 空间复杂度：O(1)
 * 稳定性：不稳定
 * 描述：在待排序序列找到一个最小的元素放到待排序序列的起始位置，再从剩余未排序序列重复相同操作
 */
public class SelectionSort {
    public static void selectionSort(int[] nums){
        for (int i=0;i<nums.length-1;i++){
            int min = i;
            // 找到最小值位置
            for (int j=i+1;j<nums.length;j++){
                if (nums[j]<nums[min]){
                    min = j;
                }
            }
            // 将找到的最小值交换到待排序起始位置
            int temp = nums[i];
            nums[i] = nums[min];
            nums[min] = temp;
        }
    }
}
  1. 希尔排序
/**
 * 希尔排序
 * 时间复杂度：O(n^3/2)
 * 空间复杂度：O(1)
 * 稳定性：不稳定
 * 描述：插入排序的一种，又称缩小增量排序
 * 把元素按下标的一定分量分组，对每组使用直接插入排序，
 * 随增量的减少，每组包含的关键词越来越少，当增量减到1时，整个序列恰被分成一组，算法终止
 */
public class ShellSort {
    public static void shellSort(int nums[]){
        // 初始增量设为序列长
        int gap = nums.length;
        // 当增量为1时结束
        while (gap!=1){
            // 增量折半
            gap/=2;
            // 对分组做一次直接插入排序
            for (int i=0;i<gap;i++){
                for (int j=i+gap;j<nums.length;j+=gap){
                    int temp = nums[j];
                    int k = j-gap;
                    while (k>=0&&nums[k]>temp){
                        nums[k+gap] = nums[k];
                        k-=gap;
                    }
                    nums[k+gap] = temp;
                }
            }
        }
    }
}
  1. 快速排序
/**
 * 快速排序
 * 时间复杂度：O(nlog2n)
 * 空间复杂度：O(nlog2n)
 * 稳定性：不稳定
 * 描述：一趟排序通过选取一个基准值，将要排序的数据分割成两部分，其中一部分所有元素都比另一部分小
 * 再按此方法分别对两部分进行快速排序
 */
public class QuickSort {
    public static void quickSort(int[] nums){
        sort(nums,0,nums.length-1);
    }
    public static void sort(int[] nums,int low,int high){
        int l = low;
        int h = high;
        // 选第一个元素为基准值，可以有多种取法，如果取值不好会导致时间复杂度变高
        int key = nums[l];
        // 一趟排序后已基准值为界分成两部分
        while (l<h){
            // 从前向后搜索，当大于key的值时停住
            while (l<h&&nums[l]<key){
                l++;
            }
            // 从后向前搜索，当小于key的值时停住
            while (l<h&&nums[h]>key){
                h--;
            }
            // 相等时不交换
            if (nums[l]==nums[h]&&l<h){
                l++;
            }
            else {
                // 交换位置
                swap(nums,l,h);
            }
        }
        if (l-1>low){
            // 对左边进行排序
            sort(nums,low,l-1);
        }
        if (h+1<high){
            // 对右边进行排序
            sort(nums,l+1,high);
        }

    }
    public static void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

7.堆排序

平常很少使用过堆排序，知道原理但是不会写。这次加了很多注释，记录一下。

/**
 * 堆排序
 * 时间复杂度：O(nlogn)
 * 空间复杂度：O(1)
 * 稳定性：不稳定
 * 描述：堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或大于）它的父节点
 * 堆排序的基本思想：将待排序的序列构造成一个大根堆，此时整个序列的最大值就是堆顶的根节点，
 * 将其与末尾元素交换，此时末尾就为最大值.
 * 然后将剩余n-1个元素重新构造成一个堆，再反复执行最终得到一个有序序列
 */
public class Heapsort {
    public static void sort(int[] nums){
        // 建堆
        buildHeap(nums);
        // 排序过程
        for (int j=nums.length-1;j>0;j--){
            // 将堆首交换至堆尾
            swap(nums,0,j);
            // 重新调整堆
            adjustHeap(nums,0,j);
        }
    }
    // 构建大根堆
    static void buildHeap(int[] nums){
        // 根据完全二叉树性质可推出，最后一个叶子节点为序列长度-1
        // 从最后一个叶子节点开始，逐步向上调整堆
        for (int i=nums.length/2-1;i>=0;i--){
            adjustHeap(nums,i,nums.length);
        }
    }
    // 调整大根堆
    static void adjustHeap(int[] nums,int i,int length){
        // 根节点
        int temp = nums[i];
        // i为根节点，则子节点为2*i+1和2*i+2
        for (int k=2*i+1;k<length;k=2*k+1){
            // 找左右子节点中较大的那一个，用于和父节点相比较
            if (k+1<length&&nums[k]<nums[k+1]){
                k++;
            }
            // 如果子节点大于根节点，则进行交换
            if (nums[k]>temp){
                swap(nums,i,k);
                // 交换完成后，对以子节点为根的子树进行判断
                i=k;
            }
            else {
                // 不需要交换则这个子树是符合堆的性质的
                break;
            }
        }

    }
    static void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
// 可以简易打印一棵较短的树
    static void printTree(int[] nums){
        int l = nums.length;
        int n = 1;
        int x = 2;
        for (int num:nums){
            for (int i = 0;i<l;i++){
                System.out.print(" ");
            }

            System.out.print(num);
            n++;
            if (n>=x){
                l = l/2;
                x = x*2;
                System.out.println();
            }
        }
        System.out.println();
    }
}