C++实现双向冒泡排序算法

2024-12-21 05:23:22

本文实例为大家分享了C++实现双向冒泡排序算法的具体代码，供大家参考，具体内容如下

一、概念（来源于百度百科）

传统冒泡算法原理

冒泡排序算法的运作如下：（从后往前）

1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

3.针对所有的元素重复以上的步骤，除了最后一个。

4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

双向冒泡算法原理

双向冒泡排序算法的运作如下：

1.传统冒泡气泡排序的双向进行，先让气泡排序由左向右进行，再来让气泡排序由右往左进行，如此完成一次排序的动作

2.使用left与right两个旗标来记录左右两端已排序的元素位置。

一个排序的例子如下所示：

排序前：45 19 77 81 13 28 18 19 77 11

往右排序：19 45 77 13 28 18 19 77 11 [81]

向左排序：[11] 19 45 77 13 28 18 19 77 [81]

往右排序：[11] 19 45 13 28 18 19 [77 77 81]

向左排序：[11 13] 19 45 18 28 19 [77 77 81]

往右排序：[11 13] 19 18 28 19 [45 77 77 81]

向左排序：[11 13 18] 19 19 28 [45 77 77 81]

往右排序：[11 13 18] 19 19 [28 45 77 77 81]

向左排序：[11 13 18 19 19] [28 45 77 77 81]

如上所示，括号中表示左右两边已排序完成的部份，当left >= right时，则排序完成。

二、实现程序：

#include <iostream>
#include <ctime>

const int MAX = 30;

// 交换两个数
void Swap(int &x, int &y) {
  int temp;

  temp = x;
  x = y;
  y = temp;
}

// 双向冒泡排序
void twoBubbleSort(int arr[], int len) {
  int left, right, shift, i; // shift为记录左右两端已排序的元素位置

  left = 0;
  right = len - 1;
  shift = 1;
  while(left < right) { // 往右排序
    for(i = left; i < right; i++) {
      if(arr[i] > arr[i+1]) { // 第一个数比第二个数大，交换
        Swap(arr[i], arr[i+1]);
        shift = i;
      }
    }
    right = shift;
    for(i = right-1; i >= left; i--) { // 向左排序
      if(arr[i] > arr[i+1]) { // 第一个数比第二个数大，交换
        Swap(arr[i], arr[i+1]);
        shift = i + 1;
      }
    }
    left = shift;
  }
}

int main(int argc, const char * argv[]) {
  // insert code here...
  int arr[MAX], i;

  srand((int)time(NULL)); // 设置时间为随机点
  std::cout << "排序前:";
  for(i = 0; i < MAX; i++) {
    arr[i] = rand() % 100;
    std::cout << arr[i] << " ";
  }

  // 调用双向冒泡排序函数
  twoBubbleSort(arr, MAX);

  std::cout << "\n排序后：";
  for(i = 0; i < MAX; i++)
    std::cout << arr[i] << " ";
  std::cout << std::endl;
  return 0;
}

运行结果：

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

C++实现的归并排序算法详解

本文实例讲述了C++实现的归并排序算法.分享给大家供大家参考,具体如下: 归并排序归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法. 该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列: 即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. 归并过程 1.比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到temp[k]中,并令i
C++使用一个栈实现另一个栈的排序算法示例

本文实例讲述了C++用一个栈实现另一个栈的排序算法.分享给大家供大家参考,具体如下: 题目: 一个栈中元素类型为整型,现在想将该栈从顶到底按从小到大的顺序排序,只许申请一个辅助栈. 除此之外,可以申请新的变量,但不能申请额外的数据结构.如何完成排序? 算法C++代码: class Solution { public: //借助一个临时栈排序源栈 static void sortStackByStack(stack<int>& s) { stack<int>* sTemp =
c++ 快速排序算法【过程图解】

第一.算法描述快速排序由C. A. R. Hoare在1962年提出,该算法是目前实践中使用最频繁,实用高效的最好排序算法, 快速排序算法是采用分治思想的算法,算法分三个步骤 1.从数组中抽出一个元素作为基数v(我们称之为划界元素),一般是取第一个.最后一个元素或中间的元素 2.将剩余的元素中小于v的移动到v的左边,将大于v元素移动到v的右边 3.对左右两个分区重复以上步骤直到所有元素都是有排序好. 第二.算法实现 /*序列划分函数*/ int partition(int a[], int p
C/C++实现双路快速排序算法原理

看了刘宇波的视频,讲双路快速排序的,原理讲的很直观,程序讲解也一看就懂.这里写一下自己的理解过程,也加深一下自己的理解. 首先说一下为什么需要双路排序,在有些带有许多重复数据的数组里,使用随机快速排序或者最简单的快速排序算法时,由于重复的数据会放在原来的索引位置不动,就回导致划分数组时划分的某一部分太长,起不到分段排序的效果,这样就导致算法退化成O(n^2)的复杂度.就像下图: 为了解决这个问题,双路快速排序采用的方法是对等于v的数也进行交换,原理如下所述: 首先选择一个数作为标志,放在数组的最
C++排序算法之插入排序

本文实例为大家分享了C++排序算法之插入排序的具体代码,供大家参考,具体内容如下 1.基本思想:将未排序的数据元素按大小顺序插入到已排好序数据序列中,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入. 例如:对2, 4, 3, 1, 6, 5进行插入排序.进行排序前,默认2是有序的,为有序区,而4, 3, 1, 6, 5是无序的,为无序区.将这五个无序的数按从小到大的顺序插入到有序区. 第一趟排序:将4与有序区的2比较,若小于2则插到2前面,大于2插到2后面.操作后有序区为:{2,
C++堆排序算法实例详解

本文实例讲述了C++堆排序算法.分享给大家供大家参考,具体如下: 堆中元素的排列方式分为两种:max-heap或min-heap,前者每个节点的key都大于等于孩子节点的key,后者每个节点的key都小于等于孩子节点的key. 由于堆可以看成一个完全二叉树,可以使用连续空间的array来模拟完全二叉树,简单原始的实现如下: #include<iostream> int heapsize=0;//全局变量记录堆的大小 void heapSort(int array[],int n){ void
C++选择排序算法实例详解

本文实例为大家分享了C++选择排序算法的具体代码,供大家参考,具体内容如下基本思想每一趟从无序区中选出最小的元素,顺序放在有序区的最后,直到全部元素排序完毕. 由于选择排序每一趟总是从无序区中选出全局最小(或最大)的元素,所以适用于从大量元速度中选择一部分排序元素.例如,从10000个元素中选出最小的前10位元素. 直接选择排序 1.排序思路从第i趟开始,从当前无序区arr[i-n-1]中选出最小元素arr[k],将它与有序区的最后一个元素,也就是无序区的第一个元素交换.每趟排序后,有序区
C++插入排序算法实例详解

本文实例为大家分享了C++插入排序算法实例的具体代码,供大家参考,具体内容如下基本思想每次将一个待排序的元素,按其大小插入到已经排好序的子序列的适当位置,知道全部元素插入完成为止. 直接插入排序 1.排序思路 arr[0...i-1]为有序区(刚开始时i=1,有序区只有arr[0]一个元素),arr[i...size]为待排序区,每次将待排序区的第一个元素arr[i]插入到有序区中的适当位置,每趟操作都使有序区增加一个元素,待排序区减少一个元素. 2.排序算法 void InsertSort
C++实现归并排序算法

归并归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. 算法描述归并操作的工作原理如下: 1.申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 2.设定两个指针,最初位置分别为两个已经排序序列的起始位置 3.比较两个指针所指向的元素,选择相对小
C/C++实现三路快速排序算法原理

书接上文,上次讲到了双路快速排序,双路快速排序是将等于v(标志数)的数也进行交换,从而避免了在处理有大量重复数据的数组分组时的不平衡.而三路快速排序则是将等于v的数也分成一组,同样可以解决上述问题.其原理如下: 1.采用随机排序的方法将某个数作为分割数,放在数组开头,该数定义为v.将小于v的一段数组开头的数索引定义为lt,将需要遍历的数组的索引定义为i,将小于v的一段数组的索引定义为gt,数组的开头和结尾的索引分别为l和r.原理图如下: 2.对索引i进行维护,逐个比较索引i对应的数与v的关系.如

C++实现双向冒泡排序算法

相关推荐

随机推荐