排序

2020-03-26 本文已影响0人 yaco

常见排序算法

冒泡排序
插入排序
选择排序
快速排序
归并排序
堆排序
桶排序
对数器

冒泡排序

基本思想：元素两两之间进行比较，较大的元素沉入后面，每轮遍历都会将最大的数沉入数组最后一位。
时间复杂度：O（N2），空间复杂度O（1）
代码：

    // 冒泡排序
   public static void bubbleSort(int[] arr) {
       if (arr == null || arr.length < 2) {
           return;
       }
       for (int i = arr.length - 1; i > 0; i--) {
           for (int j = 0; j < i; j++) {
               if (arr[j] > arr[j + 1]) {
                   swap(arr, j, j + 1);
               }
           }
       }
   }

   // 交换元素
   public static void swap(int[] arr, int i, int j) {
       int temp = arr[i];
       arr[i] = arr[j];
       arr[j] = temp;
   }

插入排序

基本思想：从数组中第二个元素开始，如果当前元素的值小于前一个元素的值，则交换，指针移到前一个位置，继续比较。
复杂度分析：N2， 1，稳定排序
代码：

        // 插排
    public static void insertSort(int[] arr) {
        if (arr == null || arr.length < 2) return;
        for (int i = 1; i < arr.length; i++) {
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                swap(arr, j, j + 1);
            }
        }
    }
    
        // 交换元素
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

选择排序

基本思想：每次从当前数组中找出最小值放在数组的第一位
复杂度： N2 1 稳定排序
代码：

    // 选择排序
   public static void selectSort(int[] arr) {
       if (arr == null || arr.length < 2) return;
       for (int i = 0; i < arr.length - 1; i++) {
           int minIndex = i;
           for (int j = i + 1; j < arr.length; j++) {
               minIndex = arr[j] >= arr[minIndex] ? minIndex : j;
           }
           swap(arr,minIndex,i);
       }
   }
   
       // 交换元素
   public static void swap(int[] arr, int i, int j) {
       int temp = arr[i];
       arr[i] = arr[j];
       arr[j] = temp;
   }

快速排序(重要)

基本思想: 在数组中随机挑选出一个数，大于该数的放在数组右边，小于此数的数的放在数组左边，等于该数组的元素放在中间
时间复杂度：N* logN 不稳定排序，(可以做成稳定的，成本太大) ,空间复杂度LogN
注意：快速排序可以做到稳定性问题，但是非常难，不需要掌握，可以搜“01 stable sort”
代码：

    // 快排
   public static void quickSort2(int[] arr) {
       if(arr.length > 1){
           sortHelp(arr,0,arr.length - 1);
       }
   }

   // 对指定位置元素进行排序，构建递归
   public static void sortHelp(int[] arr, int l, int r) {
       // 当arr排序范围有意义时才执行
       if(l < r){
           // 从l到r的位置随机找出一个值
           int temp = arr[l + (int)Math.random() * (r - l + 1)];
           // 将temp加入快排主程序，小于temp放左边，等于放中间，大于放右边
           int[] p = sortProcess(arr,l,r,temp);
           // 对余下的左边进行排序（左边一定都小于右边）
           sortHelp(arr,l,p[0]);
           // 对余下的右边进行排序
           sortHelp(arr,p[1],r);
       }
   }

   // 快排主函数
   private static int[] sortProcess(int[] arr, int l, int r, int temp) {
       // 定义左右指针，表明已经加入了多少
       int less = l - 1;
       int more = r + 1;
       // 如果l指针与more指针相交，结束循环
       while(l < more){
           if(arr[l] < temp){
               // 如果当前的元素小于temp，那么放l位置的元素，扔到前面去
               swap(arr,++less,l++);
           }else if(arr[l] > temp){
               // 如果当前的元素大于temp，那么放l位置的元素，扔到后面去
               swap(arr,--more,l);
           }else{
               // 如果等于，不操作，直接移动l指针
               l++;
           }
       }
       // 将左右两个边界返回
       return new int[]{less,more};
   }
   
   // 交换元素
   private static void swap(int[] arr, int i, int j) {
       int temp = arr[i];
       arr[i] = arr[j];
       arr[j] = temp;
   }

快排应用

荷兰国旗问题：
给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边

// 荷兰国旗问题
public static void netherlandsFlags(int[] arr, int num) {
    if (arr == null || arr.length < 2) return;
    int less = -1;
    int more = arr.length;
    int cur = 0;
    while (cur < more) {
        if (arr[cur] < num) {
            swap(arr, ++less, cur++);
        } else if (arr[cur] > num) {
            swap(arr, cur, --more);
        } else {
            cur++;
        }
    }
}

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

归并排序

基本思想：分治归并的思想，将数组一分为二，先排序左边的，然后排序右边的，然后合并数组
时间复杂度： N*logN 空间复杂度 logN
注意：归并排序的额外空间复杂度可以变成O(1)，但是非常难，不需要掌握，可以搜“归并排序内部缓存法”。
代码：

    // 归并排序
   public static void mergeSort(int[] arr) {
       if (arr == null || arr.length < 2) return;
       mergeSort(arr, 0, arr.length - 1);
   }

   // 分治
   private static void mergeSort(int[] arr, int l, int r) {
       if (l == r) return;
       int mid = l + ((r -l) >> 1);
       mergeSort(arr, l, mid);
       mergeSort(arr, mid + 1, r);
       merge(arr,l,mid,r);
   }

   // 归并
   private static void merge(int[] arr, int l, int mid, int r) {
       int[] helper = new int[r - l + 1];
       int i = 0;
       int p1 = l;
       int p2 = mid + 1;
       while(p1 <= mid && p2 <= r) {
           helper[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
       }
       while(p1 <= mid) {
           helper[i++] = arr[p1++];
       }
       while(p2 <= r) {
           helper[i++] = arr[p2++];
       }
       //将辅助的数组拷贝回原数组中
       for (int j = 0; j < helper.length; j++) {
           arr[l + j] = helper[j];
       }
   }

归并排序应用

一、小和问题
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组
的小和
例子：
[1,3,4,2,5]
1左边比1小的数，没有；
3左边比3小的数，1；
4左边比4小的数，1、3；
2左边比2小的数，1；
5左边比5小的数，1、3、4、2；
所以小和为1+1+3+1+1+3+4+2=16

// 分治归并的思想求解
public static int smallSum(int[] arr) {
    if (arr == null || arr.length < 2) return 0;
    return mergeSum(arr, 0, arr.length - 1);
}

// 分治（分治的时候干了两件事，一是记录小和，二是排序）
private static int mergeSum(int[] arr, int l, int r) {
    if (l == r) return 0;
    int mid = l + ((r - l) >> 1);
    return mergeSum(arr, l, mid) + mergeSum(arr, mid + 1, r) + merge(arr, l, mid, r);
}

// 归并
private static int merge(int[] arr, int l, int mid, int r) {
    int helper[] = new int[r - l + 1];
    int i = 0;
    int p1 = l;
    int p2 = mid + 1;
    int ans = 0;
    // 如果p1位的元素小于p2位的元素，那么p2位之后所有元素都比p1位大
    while (p1 <= mid && p2 <= r) {
        ans += arr[p1] < arr[p2] ? (arr[p1] * (r - p2 + 1)) : 0;
        helper[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
    }
    while (p1 <= mid) {
        helper[i++] = arr[p1++];
    }
    while (p2 <= r) {
        helper[i++] = arr[p2++];
    }
    for (int j = 0; j < helper.length; j++) {
        arr[l + j] = helper[j];
    }
    return ans;
}

二、数组中的逆序对（leecode面试题51（hard））
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。


// 逆序对问题
public static List<List<Integer>> reversePairs(int[] arr){
    List<List<Integer>> ans = new ArrayList<>();
    if(arr.length > 1) {
        ans = getAns(arr, 0, arr.length - 1);
    }
    return ans;
}

// 分治
private static List<List<Integer>> getAns(int[] arr, int l, int r) {
    List<List<Integer>> ans = new ArrayList<>();
    if(l == r) return ans;
    int mid = l + ((r - l) >> 1);

    List<List<Integer>> left = getAns(arr,l,mid);       // 求出左边的所有逆序对
    List<List<Integer>> right = getAns(arr,mid+1,r);  // 求出右边的所有逆序对
    List<List<Integer>> middle = merge(arr,l,r,mid);    // 合并之后的逆序对
    // 将三个部分分别加入结果集
    if(left.size() > 0){
        ans.addAll(left);
    }
    if(right.size() > 0){
        ans.addAll(right);
    }
    if(middle.size() > 0){
        ans.addAll(middle);
    }
    return ans;
}

// 合并所有的逆序对
private static List<List<Integer>> merge(int[] arr, int l, int r, int mid) {
    List<List<Integer>> ans = new ArrayList<>();
    int[] help = new int[r - l + 1];
    int p1 = l;
    int p2 = mid + 1;
    int index = 0;
    while(p1 <= mid && p2 <= r){
        if(arr[p1] < arr[p2]){
            // 此时p2后面的所有元素，都比p1大
            for (int i = p2; i <= r; i++) {
                List<Integer> temp = new ArrayList<>();
                temp.add(arr[p1]);
                temp.add(arr[i]);
                ans.add(temp);
            }
            help[index++] = arr[p1++];
        }else{
            help[index++] = arr[p2++];
        }
    }
    while(p1 <= mid){
        help[index++] = arr[p1++];
    }
    while(p2 <= r){
        help[index++] = arr[p2++];
    }
    for (int i = 0; i < help.length; i++) {
        arr[l + i] = help[i];
    }
    return ans;
}

// 编写测试类
public static void main(String[] args) {
    int[] arr = {1,7,3,9,5,6};
    List<List<Integer>> res = reversePairs(arr);
    for (List<Integer> re : res) {
        System.out.println(re.toString());
    }
}

堆排序

基本思想：首先将数组构造成为一个大顶堆；然后将堆顶最大的元素放入数组尾部，然后重新构造堆；重复沉底的操作。
时间复杂度： N*logN，空间复杂度： 1（原地排序）
代码：

    // 堆排序
   public static void heapSort(int[] arr) {
       if (arr == null || arr.length < 2) {
           return;
       }
       // 建堆过程  O（N）时间复杂度
       for (int i = 0; i < arr.length; i++) {
           heapInsert(arr,i);
       }
       // 交换数组头尾的元素位置，使得最大的元素沉入数组尾部
       int size = arr.length;
       swap(arr,0,--size);
       // 循环遍历调整--heapSize长度的数组成为大顶堆
       while(size > 0){
           heapFind(arr,size);
           swap(arr,0,--size);
       }
   }

   // 重新调整为大顶堆
   private static void heapFind(int[] arr, int size) {
       int left = 1;
       int index = 0;
       int largest = 0;
       while(left < size) {
           largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
           largest = arr[largest] > arr[index] ? largest : index;
           if(largest == index) break;
           swap(arr, largest, index);
           index = largest;
           left = (index * 2) + 1;
       }
   }

   // 向数组中插入元素构造称为大顶堆
   public static void heapInsert(int[] arr, int index) {
       while (arr[index] > arr[(index - 1) / 2]) {
           // 如果当前元素的值大于其父节点的值，那么将此元素调正到父节点的位置
           swap(arr, index, (index - 1) / 2);
           index = (index - 1) / 2;
       }
   }

   // 交换两个元素的位置
   private static void swap(int[] arr, int i, int j) {
       int temp = arr[i];
       arr[i] = arr[j];
       arr[j] = temp;
   }

桶排序

基本思想：将数组元素放在不同的桶里面，然后根据桶的下标去除元素，实现排序的目标
时间复杂度：N 空间复杂度： N 与实际数据样本有关
代码:

public static void bucketSort(int[] arr) {
    if(arr == null || arr.length < 2) {
        return;
    }
    // 找出数组中元素的最大值
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < arr.length; i++) {
        max =  Math.max(max,arr[i]);
    }
    // 创建max + 1个桶，用数组表示
    int[] bucket = new int[max + 1];
    // 将数组元素填入桶中
    for (int i = 0; i < arr.length; i++) {
        bucket[arr[i]]++;
    }
    // 将桶中元素取回，填回数组元素中
    int j = 0;
    for (int i = 0; i < bucket.length; i++) {
        while(bucket[i]-- > 0){
            arr[j++] = i;
        }
    }
}

桶排序的实际应用

一、相邻元素最大间距问题 (leeCode164. 最大间距)
给定一个数组，求如果排序之后，相邻两个数的最大差值，要求时间复杂度N，且要求不能用非基于比较的排序方法

分析：典型的桶排序案例，一共有n个数，创建n+1个桶，让第一个桶和最后一个桶保证有元素，则最大的间隔一定回在有空桶的情况下出现。

    // 桶思想解决最大间距问题
public static int maxGap(int[] arr) {
    if(arr == null || arr.length < 2) {
        return 0;
    }
    // 找出数组中的最大值和最小值，用于确定数据所在的桶号
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    int len = arr.length;
    for (int i = 0; i < len; i++) {
        min = Math.min(min,arr[i]);
        max = Math.max(max,arr[i]);
    }
    if(min == max) return 0;
    boolean[] hasNum = new boolean[len + 1]; //用于检测数组是否已经存在以元素
    int[] maxs = new int[len + 1];  //用于存放每个桶中最大的数
    int[] mins = new int[len + 1];  //用于存放每个桶中最小的数
    int bid = 0; //计算桶数
    for (int i = 0; i < len; i++) {
        bid = getBucket(arr[i],len,min,max);
        mins[bid] = hasNum[bid] ? Math.min(mins[bid],arr[i]) : arr[i];
        maxs[bid] = hasNum[bid] ? Math.max(maxs[bid],arr[i]) : arr[i];
        hasNum[bid] = true;
    }
    int res = 0; //计算结果
    int lastMax = maxs[0];  //第一个桶中肯定有元素
    int i = 1;
    for (; i < len + 1; i++) {
        if(hasNum[i]) {  // 如果桶不为空格
            res = Math.max(res, mins[i] - lastMax);
            lastMax = maxs[i];
        }
    }
    return res;
}

private static int getBucket(long num, long len, long min, long max) {
    return (int)((num - min) * len / (max - min));
}

补充

关于排序的几点补充内容：

排序的使用情况分析：

当样本量小于60时，一般采用插入排序，因为他的常熟项最低。

当大样本量的基本数组类型进行排序时，默认使用快排，他是一种不稳定排序，对基本数组类型不会产生影响。

当对大样本的自定义的对象进行排序时，默认使用归并排序，可以保证空间的稳定性。

master公式的理解：（求解递归程序的时间复杂度）
如果 T（N) = a * T(N / b) + O(N^d);那么时间复杂的计算公式如下：

log(b,a) > d -> 复杂度为O(N^log(b,a))

log(b,a) = d -> 复杂度为O(N^d * logN)

log(b,a) < d -> 复杂度为O(N^d)

排序算法的稳定性及汇总

排序算法稳定性说明

对数器的使用

功能：实现随机获取数组样本，测试排序是否正确

    // Arrays提供的方法
    public static void comparator(int[] arr) {
        Arrays.sort(arr);
    }

    // 获取随机数组（提供最大长度，和最大值）
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // 拷贝数组
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // 判断两个数组是否相等
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // 打印数组
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

      // 冒泡排序
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int e = arr.length - 1; e > 0; e--) {
            for (int i = 0; i < e; i++) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
                }
            }
        }
    }

    // 测试冒泡排序
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            bubbleSort(arr1);
            comparator(arr2);
            if (!isEqual(arr1, arr2)) {
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    }

排序

常见排序算法

冒泡排序

插入排序

选择排序

快速排序(重要)

快排应用

归并排序

归并排序应用

堆排序

桶排序

桶排序的实际应用

补充

排序算法的稳定性及汇总

对数器的使用

猜你喜欢

热点阅读