龙空技术网

Java 常见的排序算法,一次跟你说明白 ~ 快速排序

程序猿Empty 112

前言:

目前同学们对“数组打乱顺序算法怎么写”大体比较看重,小伙伴们都想要知道一些“数组打乱顺序算法怎么写”的相关文章。那么小编在网摘上收集了一些对于“数组打乱顺序算法怎么写””的相关资讯,希望大家能喜欢,看官们一起来了解一下吧!

中心思想

是由冒泡排序改进而来。在待排序的 n 个记录中任取一个记录(通常取第一个记录),把该记录放入适当位置后,数据序列被此记录划分成两部分。所有关键字比该记录关键字小的记录放置在前一部分,所有比它大的记录放置在后一部分,并把该记录在这两部分的中间(称为该记录归为)。

代码实现

private int[] quickSort(int[] arr, int left, int right) {    // System.out.println("left:"+ left +",right:"+ right)    if (left < right) {      int partitionIndex = partition(arr, left, right);      // 递归调用,对分隔后的左边数组快速排序      quickSort(arr, left, partitionIndex - 1);      // 递归调用,对分隔后的右边数组快速排序      quickSort(arr, partitionIndex + 1, right);    }    return arr;}private int partition(int[] arr, int left, int right) {    // 设定基准值(pivot)    int pivot = left;    int index = pivot + 1;    for (int i = index; i <= right; i++) {      if (arr[i] < arr[pivot]) {        swap(arr, i, index);        index++;      }    }    swap(arr, pivot, index - 1);    return index - 1;}private void swap(int[] arr, int i, int j) {    int temp = arr[i];    arr[i] = arr[j];    arr[j] = temp;}
时间复杂度最好的情况下:因为每次都将序列划分为两个部分(一般二分的复杂度跟log N相关),所以O(N*logN)。最坏的情况下:基本有序时,退化为冒泡排序,几乎要比较 N *N,所以 O(N*N)。稳定性

由于每次都需要和中轴元素交换,因此原来的顺序可能被打乱。(多个相同的元素),所以说,快速排序是不稳定的!

标签: #数组打乱顺序算法怎么写 #常见排序算法java