温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

C++如何实现快速排序算法

发布时间:2020-07-29 15:03:10 来源:亿速云 阅读:256 作者:小猪 栏目:编程语言

这篇文章主要为大家展示了C++如何实现快速排序算法,内容简而易懂,希望大家可以学习一下,学习完之后肯定会有收获的,下面让小编带大家一起来看看吧。

一、基本思想是:

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

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

// 快速排序:选第一个对象作为基准,按照该对象的排序码大小,将整个对象
// 序列划分为左右两个字序列:
// 左侧子序列中所有对象的排序码都小于或等于基准对象的排序码;
// 右侧子序列中所有对象的排序码都大于基准对象的排序码;
// 基准对象则排在这两个子序列中间,这也是该对象最终应放的位置
// 然后分别对这两个子序列重复施行上述方法,直到所有的对象都排在相应位置上为止
#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;
}

运行结果:

C++如何实现快速排序算法

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

// 快速排序的另一种方法:只往一边扫描
#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;
}

运行结果:

C++如何实现快速排序算法

以上就是关于C++如何实现快速排序算法的内容,如果你们有学习到知识或者技能,可以把它分享出去让更多的人看到。

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI