排序:当我踏上算法之路,我发现...

2020.09.26 13:09:23
40
阅读约 1 分钟

基本的排序算法都不会啊啊啊啊😫,算是凉了,为了咱的offer,记录下常用的排序算法。

排序 #

快速排序 #

感觉算是比较简单明了的版本了,起码我感觉还挺好记的,来自《数据结构与算法分析-java语言描述》。

public class Solution {
    public static void quickSort(List<Integer> items) {
        if(items.size()>1){
            List<Integer> smaller=new ArrayList<>();
            List<Integer> same=new ArrayList<>();
            List<Integer> larger=new ArrayList<>();
            // 选择枢纽元
            Integer chosen = items.get(items.size() / 2);
            for (Integer i : items) {
                if(i<chosen){
                    // 小于枢纽元,放入smaller中
                    smaller.add(i);
                }else if(i>chosen){
                    larger.add(i);
                }else {
                    same.add(i);
                }
            }
            // 递归排序smaller这部分
            quickSort(smaller);
            quickSort(larger);
            items.clear();
            items.addAll(smaller);
            items.addAll(same);
            items.addAll(larger);
        }

    }
    public static void main(String[] args) {
        int[] arr = {10, 7, 2, 4, 7, 62, 3, 4, 2, 1, 8, 9, 19};
        List<Integer> items = Arrays.stream(arr).boxed().collect(Collectors.toList());
        quickSort(items);

       items.forEach(System.out::println);
    }
}

数组排序

数组排序版本

  public static void quickSort(int[] arr,int low,int high) {
             if(low<high){
                int pivot = partition(arr,low,high);
                 quickSort(arr, low, pivot - 1);
                 quickSort(arr, pivot + 1, high);
             }
    }

    private static int partition(int[] arr, int low, int high) {
       int pivot = arr[low];
        while (low<high){
            // 遇到小值 交换
            while (low<high && arr[high]>=pivot) --high;
            arr[low] =arr[high];
            // 遇到大值 较换
            while (low<high && arr[low]<=pivot) ++low;
            arr[high] =arr[low];
        }
        arr[low] =pivot;
        return low;
    }

平均时间复杂度: nlog(n)n\log(n)

最坏:o(n2)o(n^2)

插入排序 #

真的是非常简洁好记了,不好记头给你

public class Solution {
    public int[] InsertSort(int[] a){
         int j;
        for (int p = 1; p < a.length ; p++) {
            int temp = a[p];
            for (j = p; j >0&& a[j-1] > temp ; j--) {
            // 往前找
                a[j] = a[j-1];
            }
            a[j]=temp;
        }
        return a;
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] a = solution.InsertSort(new int[]{3, 2,4,3});
        for (int anInt : a) {
            System.out.println(anInt);
        }
    }
}

直接选择排序 #

public class Solution {

    public int[] SelectSort(int[] A){
        int min;
        int temp;
        for (int i = 0; i < A.length-1; i++) {
                min=i;
            for (int j = i+1; j <A.length; j++) {
            // 往后找最小值
                if(A[j]<A[min]) min=j;
            }
            if(min!=i){
            // 交换
                temp = A[i];
                A[i] = A[min];
                A[min] = temp;
            }
        }
        return A;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] sort = solution.SelectSort(new int[]{2, 4, 3, 5, 1});
        for (int i : sort) {
            System.out.println(i);
        }
    }
}

阅读:40 . 字数:249 发布于 2 个月前
Copyright 2018-2020 Siques