首页
论坛
课程
招聘
问答 企服 专栏 CTF 众测 排行榜 知识库 工具下载 看雪峰会 看雪20年 看雪商城 证书查询
  1. 看雪论坛
  2. 编程技术
    3. 发新帖
[原创]排序算法:QuickSort以及dualPivotQuickSort的练习_java和C++源码带上!!!
2022-3-8 23:28 10523

[原创]排序算法:QuickSort以及dualPivotQuickSort的练习_java和C++源码带上!!!

黄裕顺 活跃值
2022-3-8 23:28
10523

前些日子,java网友聊排序,
谈到Java库的排序算法有双轴快排比普通快排好,
然后一个好奇,就度娘看了看原理思想,自己写着练手

说下算法核心大概思想:

QuickSort:
取一个基数,把元素划分2边,
一边小于这个基数,一边大于这个基数,
然后一直这样划分到最小,也就把所有元素排序完成了
dualPivotQuickSort:
核心思想跟上面一样,都是划分元素
不过这个有2个基数,也就是把元素划分3份

 

接下来直接分享学习源码:

C++版:经典快排

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
//交换2个元素
void QuickSort::swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
 
/**
 * 快速排序的核心算法
 * @param arr       需要排序的数组
 * @param start     排序的开始位置
 * @param end       排序的结束位置
 */
 void QuickSort::qSort(int* arr, int start, int end) {
    //防止无限递归
    if (end > start) {
        int low = start++;
        int high = end;
        int pivot = arr[low];
        //基于pivot划分位置
        while (start < end) {
            if (arr[start] < pivot) {
                start++;
            }
            else {
                this->swap(arr+start, arr+end--);
            }
        }
        //防止停止位置的值大于基数
        if (arr[start] >= pivot) {
            start--;
        }
        this->swap(arr+start, arr+low);
        //继续划分更小
        this->qSort(arr, low, start);
        this->qSort(arr, start + 1, high);
    }
}

C++版:双轴快排

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
48
49
50
51
52
53
/**
  * 双轴快速排序的核心算法
  * @param arr       需要排序的数组
  * @param start     排序的开始位置
  * @param end       排序的结束位置
  */
void QuickSort::dualPivotQuickSort(int* arr, int start, int end) {
    //如果数量太少则直接采用经典的单轴快排
    if (end - start < 64) {
        this->qSort(arr, start, end);
        return;
    }
 
    //双轴快排核心
    int low = start++;
    int high = end--;
    //先排序前面6个元素
    this->qSort(arr, low, low + 5);
    //初始化双轴的2个基数
    this->swap(arr+low, arr+low + 1);
    this->swap(arr+high, arr+low + 3);
    int pivotLow = arr[low], pivotHigh = arr[high];
    int lowIndex = low + 1, highIndex = high - 1;
 
    //基于pivot划分位置
    while (start < end) {
        //小于左边基数
        if (arr[start] < pivotLow) {
            this->swap(arr+start++, arr+lowIndex++);
        }
        //大于右边基数
        else if (arr[start] > pivotHigh) {
            this->swap(arr+start, arr+highIndex--);
            end--;
        }
        //位置2个基数中间
        else {
            start++;
        }
    }
    //修正基数位置
    --lowIndex;
    if (arr[highIndex] < pivotLow) {
        this->swap(arr+low, arr+highIndex);
    }
    else if (arr[highIndex] >= pivotHigh) {
        --highIndex;
    }
    //继续划分更小
    dualPivotQuickSort(arr, low, lowIndex);//左边
    dualPivotQuickSort(arr, lowIndex + 1, highIndex);//中间
    dualPivotQuickSort(arr, highIndex + 1, high);//右边
}

C++版:双轴快速无递归方式

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/**
  * 双轴快速排序的核心算法_去掉递归
  * @param arr       需要排序的数组
  * @param start     排序的开始位置
  * @param end       排序的结束位置
  */
void QuickSort::dualPivotQuickSortNoRecursion(int* arr, int start, int end) {
    int indexLen = pow(log2(end - start), 2) + 8;
    int current = indexLen;
    int* index = new int[indexLen+1];
SORT:
    //如果数量太少则直接采用经典的单轴快排
    if (end - start < 64) {
        this->qSort(arr, start, end);
        //判断是否全部排序完成
        if (current < indexLen){
            start = index[++current];
            end = index[++current];
            goto SORT;
        }
        else
        {
            return;
        }        
    }
 
    //双轴快排核心
    int low = start++;
    int high = end--;
    //先排序前面6个元素
    this->qSort(arr, low, low + 5);
    //初始化双轴的2个基数
    this->swap(arr + low, arr + low + 1);
    this->swap(arr + high, arr + low + 3);
    int pivotLow = arr[low], pivotHigh = arr[high];
    int lowIndex = low + 1, highIndex = high - 1;
 
    //基于pivot划分位置
    while (start < end) {
        //小于左边基数
        if (arr[start] < pivotLow) {
            this->swap(arr + start++, arr + lowIndex++);
        }
        //大于右边基数
        else if (arr[start] > pivotHigh) {
            this->swap(arr + start, arr + highIndex--);
            end--;
        }
        //位置2个基数中间
        else {
            start++;
        }
    }
    //修正基数位置
    --lowIndex;
    if (arr[highIndex] < pivotLow) {
        this->swap(arr + low, arr + highIndex);
    }
    else if (arr[highIndex] >= pivotHigh) {
        --highIndex;
    }
    //分割位置_最大
    index[current--] = high;
    index[current--] = highIndex + 1;
    //分割位置_中间
    index[current--] = highIndex;
    index[current--] = lowIndex + 1;
    //分割位置_最小
    end = lowIndex;
    start = low;
    goto SORT;
}

其实,这些东西,我真心用不上
只是刚好网友聊到,自己失业没事做,陪着他玩了,
感觉这些知道下概念就行,真写都用别人封装好的
java的也写了一份,一起分享了吧

java版:经典快排

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
/**
    * 快速排序的核心算法
    * @param arr       需要排序的数组
    * @param start     排序的开始位置
    * @param end       排序的结束位置
    */
   public void qSort(int[] arr,int start,int end){
       //防止无限递归
       if(end>start){
           int low =start++;
           int high = end;
           int pivot =arr[low];
           //基于pivot划分位置
           while (start < end){
               if (arr[start] < pivot){
                   start++;
               }else {
                   swap(arr,start,end--);
               }
           }
           //防止停止位置的值大于基数
           if (arr[start] >= pivot){
               start--;
           }
           swap(arr,start,low);
           //继续划分更小
           qSort(arr,low,start);
           qSort(arr,start+1,high);
       }
   }
 
   /**
    * 交换数组中的2个元素
    * @param arr       数组
    * @param indexA    元素A的位置
    * @param indexB    元素B的位置
    */
   public void swap(int[] arr,int indexA,int indexB){
       int temp = arr[indexA];
       arr[indexA] = arr[indexB];
       arr[indexB]=temp;
   }

java版:双轴快排

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
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
   * 快速排序
   * @param arr 需要排序的数组
   */
  public void quickSort(int[] arr){
      dualPivotQuickSort(arr,0,arr.length-1);
  }
 
  /**
   * 双轴快速排序的核心算法
   * @param arr       需要排序的数组
   * @param start     排序的开始位置
   * @param end       排序的结束位置
   */
  public void dualPivotQuickSort(int[] arr,int start,int end){
      //如果数量太少则直接采用经典的单轴快排
      if (end-start < 64) {
          qSort(arr,start,end);
          return;
      }
 
      //双轴快排核心
      int low =start++;
      int high = end--;
      //先排序前面6个元素
      qSort(arr,low,low+5);
      //初始化双轴的2个基数
      swap(arr,low,low+1);
      swap(arr,high,low+3);
      int pivotLow =arr[low],pivotHigh =arr[high];
      int lowIndex =low+1,highIndex=high-1;
 
      //基于pivot划分位置
      while (start < end){
          //小于左边基数
          if (arr[start] < pivotLow){
              swap(arr,start++,lowIndex++);
          }
          //大于右边基数
          else if(arr[start] > pivotHigh){
              swap(arr,start,highIndex--);
              end--;
          }
          //位置2个基数中间
          else{
              start++;
          }
      }
      //修正基数位置
      --lowIndex;
      if (arr[highIndex] < pivotLow ) {
          swap(arr,low,highIndex);
      }else if (arr[highIndex] >= pivotHigh){
          --highIndex;
      }
      //继续划分更小
      dualPivotQuickSort(arr,low,lowIndex);//左边
      dualPivotQuickSort(arr,lowIndex+1,highIndex);//中间
      dualPivotQuickSort(arr,highIndex+1,high);//右边
  }

Unidbg 模拟执行精讲

收藏
点赞・2
打赏
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
　回帖　 表情 雪币赚取及消费
高级回复
返回