欢迎访问优讯网!
您当前的位置:首页 > 爱编程

C++实现快速排序(Quicksort)算法

时间:2020-04-28 09:28:21  来源:优讯网  作者:小卡司  浏览次数:
这篇文章主要为大家详细介绍了C++实现快速排序(Quicksort)算法,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
 

本文实例为大家分享了Android九宫格图片展示的具体代码,供大家参考,具体内容如下

一、基本思想是:

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

二、方法1实现程序:左右两个方向扫描

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
// 快速排序:选第一个对象作为基准,按照该对象的排序码大小,将整个对象
// 序列划分为左右两个字序列:
// 左侧子序列中所有对象的排序码都小于或等于基准对象的排序码;
// 右侧子序列中所有对象的排序码都大于基准对象的排序码;
// 基准对象则排在这两个子序列中间,这也是该对象最终应放的位置
// 然后分别对这两个子序列重复施行上述方法,直到所有的对象都排在相应位置上为止
#include <iostream>
  
// 一次快速排序算法
int quickPass(int arr[], int low, int high) {
  int down, up, temp;
   
  down = low;
  up = high;
  temp = arr[low];
  while(down < up) {
    while((down < up) && arr[up] >= temp) // 从右向左扫描
      up--;
    if(down < up)
      arr[down++] = arr[up]; // 在被腾空出来的单元(由down指向)中填入arr[up]
    while((down < up) && arr[down] < temp) // 从左向右扫描
      down++;
    if(down < up)
      arr[up--] = arr[down]; // 在被腾空出来的单元(由up指向)中填入arr[down]
  }
  arr[down] = temp; // 最后把基准插回到数组中间去
  return down;
}
  
// 快速排序算法
void quickSort(int arr[], int low, int high) {
  // 对序列arr[low]到arr[high]作快速排序
  int mid;
   
  if(low < high) {
    mid = quickPass(arr, low, high); // 对序列arr[low]到arr[high]作一趟快速排序
    quickSort(arr, low, mid-1); // 对左半部分作递归处理
    quickSort(arr, mid+1, high); // 对右半部分作递归处理
  }
}
  
int main(int argc, const char * argv[]) {
  // insert code here...
  int len, i;
  int arr[] = {40, 30, 60, 90, 70, 10, 20, 40};
   
  len = sizeof(arr) / sizeof(arr[0]);
  std::cout << "排序前:\n";
  for(i = 0; i < len; i++)
    std::cout << arr[i] << " ";
  std::cout << std::endl;
  
  quickSort(arr, 0, len-1); // 调用快速排序法
   
  std::cout << "排序后:\n";
  for(i = 0; i < len; i++)
    std::cout << arr[i] << " ";
  std::cout << std::endl;
  return 0;
}

运行结果:

三、方法2:只往一边扫描

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
// 快速排序的另一种方法:只往一边扫描
#include <iostream>
  
// 交换两个数
void Exchange(int &a, int &b) {
  int temp;
   
  temp = a;
  a = b;
  b = temp;
}
  
// 将序列分为左右两部分,左部分较小,右部分较大
int Partition(int arr[], int low, int high) {
  int x, i, j;
   
  x = arr[high]; // 以high位置的数作为基准
  i = low - 1;
     // 进行数据分类:左部分较小,右部分较大
  for(j = low; j < high; j++)
    if(arr[j] <= x) { // 往右扫描找小于或者等于基准的数
      i = i + 1;
      Exchange(arr[i], arr[j]); // 交换
    }
  Exchange(arr[i+1], arr[high]); // 把基准放到中间
  return i+1;
}
  
// 快速排序算法
void quickSort(int arr[], int low, int high) {
  int q;
   
  if(low < high) {
    q = Partition(arr, low, high);
    quickSort(arr, low, q-1);
    quickSort(arr, q+1, high);
  }
}
  
int main(int argc, const char * argv[]) {
  int len, i;
  int arr[] = {40, 30, 60, 90, 70, 10, 20, 40};
   
  len = sizeof(arr) / sizeof(arr[0]);
  std::cout << "排序前:\n";
  for(i = 0; i < len; i++)
    std::cout << arr[i] << " ";
  std::cout << std::endl;
  quickSort(arr, 0, len-1); // 调用快速排序法
   
  std::cout << "排序后:\n";
  for(i = 0; i < len; i++)
    std::cout << arr[i] << " ";
  std::cout << std::endl;
  return 0;
}

运行结果:

以上就是本文的全部内容,希望对大家的学习有所帮助

来顶一下
返回首页
返回首页

原文链接:https://www.jb51.net/article/185594.htm


推荐资讯
如何下载旧版centos iso镜像 如何下载迷你mini版的centos镜像
如何下载旧版centos i
计算机的正确使用姿势 电脑痴如何正确的使用电脑
计算机的正确使用姿势
好用的后台管理的前端框架模版H-ui H-ui框架模版分享
好用的后台管理的前端
微信电脑多开方法 无需辅助电脑版微信双开方法分享
微信电脑多开方法 无
相关文章
栏目更新
栏目热门