算法

快速排序法

Posted by アライさん on 2019年10月22日

思路：
选择一个基准值array[(startIndex + endIndex) / 2]，比基准值小的挪到左边，比基准值大的挪到右边。
对左边、右边，再分别用递归进行这种处理。
基准值可以取array[0]，但如果数组为已经逆序排序，快速排序的效率就会变成冒泡排序。
快速排序在最糟糕的情况下，效率等于冒泡排序。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
fun quickSort(array: IntArray, startIndex: Int, endIndex: Int) {
    //开始元素下标小于等于结束元素下标
    if (startIndex >= endIndex) {
        return
    }

    var leftIndex = startIndex
    var rightIndex = endIndex
    //取中间值作为判断基准
    val middleValue = array[(leftIndex + rightIndex) / 2]

    //左右下标逐渐接近，但左侧元素下标大于右侧元素时，就完成了一次分割
    while (leftIndex <= rightIndex){
        //找到左侧比中间值大的值
       while (array[leftIndex] < middleValue){
           ++leftIndex
       }

        //找到右侧比中间值小的值
        while (array[rightIndex] > middleValue){
            --rightIndex
        }

        //比中间值大的在左侧，比中间值小的在右侧，交换两者
        if (leftIndex < rightIndex){
            val tmp = array[leftIndex]
            array[leftIndex] = array[rightIndex]
            array[rightIndex] = tmp

            //调换之后，继续判断剩余元素
            ++leftIndex
            --rightIndex

        }else if (leftIndex == rightIndex){
            //leftIndex和rightIndex最终一定会相遇
            //给leftIndex增加1，满足跳出循环的条件
            ++leftIndex
        }

    }

    //当leftIndex == rightIndex时，++leftIndex， 所以leftIndex已经越过rightIndex
    //leftIndex和rightIndex并没有平均分割数据
    quickSort(array,startIndex,rightIndex)
    quickSort(array,leftIndex,endIndex)

}

## dart实现 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//由大到小排序
  quickSort(List<int> list,int beginIndex,int endIndex){
    //左侧下标小于等于右侧下标，代表需要排序的元素少于等于1个，无需排序
    if(beginIndex >= endIndex || list.isEmpty){
      return;
    }

    //取中间值
    int middle = list[(beginIndex+endIndex)~/2];
    int leftIndex = beginIndex;
    int rightIndex = endIndex;

    //左值小于右值，继续循环
    while(leftIndex <= rightIndex) {

      while (list[leftIndex] > middle) {
        ++leftIndex;
      }

      while (list[rightIndex] < middle) {
        --rightIndex;
      }

      if (leftIndex < rightIndex) {
        int tmp = list[leftIndex];
        list[leftIndex] = list[rightIndex];
        list[rightIndex] = tmp;
        ++leftIndex;
        --rightIndex;
      } else if (leftIndex == rightIndex) {
        ++leftIndex;
      }
    }
    quickSort(list, leftIndex, endIndex);
    quickSort(list, beginIndex, rightIndex);

  }



Tags
算法