C++实现八个常用的排序算法:插入排序、冒泡排序、选择排序、希尔排序等

本文实现了八个常用的排序算法:插入排序、冒泡排序、选择排序、希尔排序 、快速排序、归并排序、堆排序和LST基数排序

首先是算法实现文件Sort.h,代码如下:

/*
* 实现了八个常用的排序算法:插入排序、冒泡排序、选择排序、希尔排序
* 以及快速排序、归并排序、堆排序和LST基数排序
* @author gkh178
*/
#include <iostream> 

template<class T>
void swap_value(T &a, T &b)
{
  T temp = a;
  a = b;
  b = temp;
} 

//插入排序:时间复杂度o(n^2)
template<class T>
void insert_sort(T a[], int n)
{
  for (int i = 1; i < n; ++i)
  {
    T temp = a[i];
    int j = i - 1;
    while (j >= 0 && a[j] > temp)
    {
      a[j + 1] = a[j];
      --j;
    }
    a[j + 1] = temp;
  }
} 

//冒泡排序:时间复杂度o(n^2)
template<class T>
void bubble_sort(T a[], int n)
{
  for (int i = n - 1; i > 0; --i)
  {
    for (int j = 0; j < i; ++j)
    {
      if (a[j] > a[j + 1])
      {
        swap_value(a[j], a[j + 1]);
      }
    }
  }
} 

//选择排序:时间复杂度o(n^2)
template<class T>
void select_sort(T a[], int n)
{
  for (int i = 0; i < n - 1; ++i)
  {
    T min = a[i];
    int index = i;
    for (int j = i + 1; j < n; ++j)
    {
      if (a[j] < min)
      {
        min = a[j];
        index = j;
      }
    }
    a[index] = a[i];
    a[i] = min;
  }
} 

//希尔排序:时间复杂度介于o(n^2)和o(nlgn)之间
template<class T>
void shell_sort(T a[], int n)
{
  for (int gap = n / 2; gap >= 1; gap /= 2)
  {
    for (int i = gap; i < n; ++i)
    {
      T temp = a[i];
      int j = i - gap;
      while (j >= 0 && a[j] > temp)
      {
        a[j + gap] = a[j];
        j -= gap;
      }
      a[j + gap] = temp;
    }
  }
} 

//快速排序:时间复杂度o(nlgn)
template<class T>
void quick_sort(T a[], int n)
{
  _quick_sort(a, 0, n - 1);
}
template<class T>
void _quick_sort(T a[], int left, int right)
{
  if (left < right)
  {
    int q = _partition(a, left, right);
    _quick_sort(a, left, q - 1);
    _quick_sort(a, q + 1, right);
  }
}
template<class T>
int _partition(T a[], int left, int right)
{
  T pivot = a[left];
  while (left < right)
  {
    while (left < right && a[right] >= pivot)
    {
      --right;
    }
    a[left] = a[right];
    while (left < right && a[left] <= pivot)
    {
      ++left;
    }
    a[right] = a[left];
  }
  a[left] = pivot;
  return left;
} 

//归并排序:时间复杂度o(nlgn)
template<class T>
void merge_sort(T a[], int n)
{
  _merge_sort(a, 0, n - 1);
}
template<class T>
void _merge_sort(T a[], int left, int right)
{
  if (left < right)
  {
    int mid = left + (right - left) / 2;
    _merge_sort(a, left, mid);
    _merge_sort(a, mid + 1, right);
    _merge(a, left, mid, right);
  }
}
template<class T>
void _merge(T a[], int left, int mid, int right)
{
  int length = right - left + 1;
  T *newA = new T[length];
  for (int i = 0, j = left; i <= length - 1; ++i, ++j)
  {
    *(newA + i) = a[j];
  }
  int i = 0;
  int j = mid - left + 1;
  int k = left;
  for (; i <= mid - left && j <= length - 1; ++k)
  {
    if (*(newA + i) < *(newA + j))
    {
      a[k] = *(newA + i);
      ++i;
    }
    else
    {
      a[k] = *(newA + j);
      ++j;
    }
  }
  while (i <= mid - left)
  {
    a[k++] = *(newA + i);
    ++i;
  }
  while (j <= right - left)
  {
    a[k++] = *(newA + j);
    ++j;
  }
  delete newA;
} 

//堆排序:时间复杂度o(nlgn)
template<class T>
void heap_sort(T a[], int n)
{
  built_max_heap(a, n);//建立初始大根堆
  //交换首尾元素,并对交换后排除尾元素的数组进行一次上调整
  for (int i = n - 1; i >= 1; --i)
  {
    swap_value(a[0], a[i]);
    up_adjust(a, i);
  }
}
//建立一个长度为n的大根堆
template<class T>
void built_max_heap(T a[], int n)
{
  up_adjust(a, n);
}
//对长度为n的数组进行一次上调整
template<class T>
void up_adjust(T a[], int n)
{
  //对每个带有子女节点的元素遍历处理,从后到根节点位置
  for (int i = n / 2; i >= 1; --i)
  {
    adjust_node(a, n, i);
  }
}
//调整序号为i的节点的值
template<class T>
void adjust_node(T a[], int n, int i)
{
  //节点有左右孩子
  if (2 * i + 1 <= n)
  {
    //右孩子的值大于节点的值,交换它们
    if (a[2 * i] > a[i - 1])
    {
      swap_value(a[2 * i], a[i - 1]);
    }
    //左孩子的值大于节点的值,交换它们
    if (a[2 * i - 1] > a[i - 1])
    {
      swap_value(a[2 * i - 1], a[i - 1]);
    }
    //对节点的左右孩子的根节点进行调整
    adjust_node(a, n, 2 * i);
    adjust_node(a, n, 2 * i + 1);
  }
  //节点只有左孩子,为最后一个有左右孩子的节点
  else if (2 * i == n)
  {
    //左孩子的值大于节点的值,交换它们
    if (a[2 * i - 1] > a[i - 1])
    {
      swap_value(a[2 * i - 1], a[i - 1]);
    }
  }
} 

//基数排序的时间复杂度为o(distance(n+radix)),distance为位数,n为数组个数,radix为基数
//本方法是用LST方法进行基数排序,MST方法不包含在内
//其中参数radix为基数,一般为10;distance表示待排序的数组的数字最长的位数;n为数组的长度
template<class T>
void lst_radix_sort(T a[], int n, int radix, int distance)
{
  T* newA = new T[n];//用于暂存数组
  int* count = new int[radix];//用于计数排序,保存的是当前位的值为0 到 radix-1的元素出现的的个数
  int divide = 1;
  //从倒数第一位处理到第一位
  for (int i = 0; i < distance; ++i)
  {
    //待排数组拷贝到newA数组中
    for (int j = 0; j < n; ++j)
    {
      *(newA + j) = a[j];
    }
    //将计数数组置0
    for (int j = 0; j < radix; ++j)
    {
      *(count + j) = 0;
    }
    for (int j = 0; j < n; ++j)
    {
      int radixKey = (*(newA + j) / divide) % radix; //得到数组元素的当前处理位的值
      (*(count + radixKey))++;
    }
    //此时count[]中每个元素保存的是radixKey位出现的次数
    //计算每个radixKey在数组中的结束位置,位置序号范围为1-n
    for (int j = 1; j < radix; ++j)
    {
      *(count + j) = *(count + j) + *(count + j - 1);
    }
    //运用计数排序的原理实现一次排序,排序后的数组输出到a[]
    for (int j = n - 1; j >= 0; --j)
    {
      int radixKey = (*(newA + j) / divide) % radix;
      a[*(count + radixKey) - 1] = newA[j];
      --(*(count + radixKey));
    }
    divide = divide * radix;
  }
}

然后是测试文件main.cpp,代码如下:

#include "Sort.h"
using namespace std; 

template<class T>
void printArray(T a[], int n)
{
  for (int i = 0; i < n; ++i)
  {
    cout << a[i] << " ";
  }
  cout << endl;
} 

int main()
{
  for (int i = 1; i <= 8; ++i)
  {
    int arr[] = { 45, 38, 26, 77, 128, 38, 25, 444, 61, 153, 9999, 1012, 43, 128 };
    switch (i)
    {
    case 1:
      insert_sort(arr, sizeof(arr) / sizeof(arr[0]));
      break;
    case 2:
      bubble_sort(arr, sizeof(arr) / sizeof(arr[0]));
      break;
    case 3:
      select_sort(arr, sizeof(arr) / sizeof(arr[0]));
      break;
    case 4:
      shell_sort(arr, sizeof(arr) / sizeof(arr[0]));
      break;
    case 5:
      quick_sort(arr, sizeof(arr) / sizeof(arr[0]));
      break;
    case 6:
      merge_sort(arr, sizeof(arr) / sizeof(arr[0]));
      break;
    case 7:
      heap_sort(arr, sizeof(arr) / sizeof(arr[0]));
      break;
    case 8:
      lst_radix_sort(arr, sizeof(arr) / sizeof(arr[0]), 10, 4);
      break;
    default:
      break;
    }
    printArray(arr, sizeof(arr) / sizeof(arr[0]));
  }
  return 0;
}

最后是运行结果图,如下:

以上就是C++实现八个常用的排序算法的全部代码,希望大家对C++排序算法有更进一步的了解。

(0)

相关推荐

  • 全排列算法的非递归实现与递归实现的方法(C++)

    (一)非递归全排列算法基本思想是:    1.找到所有排列中最小的一个排列P.    2.找到刚刚好比P大比其它都小的排列Q,    3.循环执行第二步,直到找到一个最大的排列,算法结束.下面用数学的方法描述:给定已知序列 P =  A1A2A3An ( Ai!=Aj , (1<=i<=n  , 1<=j<=n, i != j  ) )找到P的一个最小排列Pmin = P1P2P3Pn  有  Pi > P(i-1) (1 < i <= n)从Pmin开始,总是目

  • C++堆排序算法的实现方法

    本文实例讲述了C++实现堆排序算法的方法,相信对于大家学习数据结构与算法会起到一定的帮助作用.具体内容如下: 首先,由于堆排序算法说起来比较长,所以在这里单独讲一下.堆排序是一种树形选择排序方法,它的特点是:在排序过程中,将L[n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲节点和孩子节点之间的内在关系,在当前无序区中选择关键字最大(或最小)的元素. 一.堆的定义 堆的定义如下:n个关键字序列L[n]成为堆,当且仅当该序列满足: ①L(i) <= L(2i)且L(i) <= L(2

  • 使用C++实现全排列算法的方法详解

    复制代码 代码如下: <P>不论是哪种全排列生成算法,都遵循着"原排列"→"原中介数"→"新中介数"→"新排列"的过程.</P><P>其中中介数依据算法的不同会的到递增进位制数和递减进位制数.</P><P>关于排列和中介数的一一对应性的证明我们不做讨论,这里仅仅给出了排列和中介数的详细映射方法.</P> · 递增进位制和递减进位制数  所谓递增进位制和递减

  • 基于C++实现的各种内部排序算法汇总

    提起排序算法相信大家都不陌生,或许很多人已经把它们记得滚瓜烂熟,甚至随时可以写出来.是的,这些都是最基本的算法.这里就把各种内部排序算法总结归纳了一下,包括插入排序(直接插入排序,折半插入排序,希尔排序).交换排序(冒泡排序,快速排序).选择排序(简单选择排序,堆排序).2-路归并排序.(另:至于堆排序算法,前面已经有一篇文章针对堆排序的算法实现做了详细的描述) C++实现代码如下: /*******************************************************

  • C++插入排序算法实例

    插入排序 没事喜欢看看数据结构和算法,增加自己对数据结构和算法的认识,同时也增加自己的编程基本功.插入排序是排序中比较常见的一种,理解起来非常简单.现在比如有以下数据需要进行排序: 10 3 8 0 6 9 2 当使用插入排序进行升序排序时,排序的步骤是这样的: 10 3 8 0 6 9 2 // 取元素3,去和10进行对比 3 10 8 0 6 9 2 // 由于10比3大,将10向后移动,将3放置在原来10的位置:再取8与前一个元素10进行对比 3 8 10 0 6 9 2 // 同理移动1

  • C++线性时间的排序算法分析

    前面的文章已经介绍了几种排序算法,如插入排序(直接插入排序,折半插入排序,希尔排序).交换排序(冒泡排序,快速排序).选择排序(简单选择排序,堆排序).2-路归并排序(可以参考前一篇文章:各种内部排序算法的实现)等,这些排序算法都有一个共同的特点,就是基于比较. 本文将介绍三种非比较的排序算法:计数排序,基数排序,桶排序.它们将突破比较排序的Ω(nlgn)下界,以线性时间运行. 一.比较排序算法的时间下界 所谓的比较排序是指通过比较来决定元素间的相对次序. "定理:对于含n个元素的一个输入序列,

  • C++简单实现的全排列算法示例

    本文实例讲述了C++简单实现的全排列算法.分享给大家供大家参考,具体如下: #include "stdafx.h" #include <string> #include <algorithm> #include <iostream> void func(const char *str_in) { std::string str(str_in); std::sort(str.begin(),str.end()); do { std::cout<&

  • 利用C++的基本算法实现十个数排序

    冒泡排序法原理:它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成. 冒泡排序算法的运作如下:1.比较相邻的元素.如果第一个比第二个大,就交换他们两个. 2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应该会是最大的数. 3.针对所有的元素重复以上的步骤,除了最后一个. 4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较. 示例代码:

  • C++冒泡排序算法实例

    冒泡排序 大学学习数据结构与算法最开始的时候,就讲了冒泡排序:可见这个排序算法是多么的经典.冒泡排序是一种非常简单的排序算法,它重复地走访过要排序的数列,每一次比较两个数,按照升序或降序的规则,对比较的两个数进行交换.比如现在我要对以下数据进行排序: 10 3 8 0 6 9 2 当使用冒泡排序进行升序排序时,排序的步骤是这样的: 3 10 8 0 6 9 2  // 10和3进行对比,10>3,交换位置 3 8 10 0 6 9 2  // 10再和8进行对比,10>8,交换位置 3 8 0

  • C++归并排序算法实例

    归并排序 归并排序算法是采用分治法的一个非常典型的应用.归并排序的思想是将一个数组中的数都分成单个的:对于单独的一个数,它肯定是有序的,然后,我们将这些有序的单个数在合并起来,组成一个有序的数列.这就是归并排序的思想.它的时间复杂度为O(N*logN). 代码实现 复制代码 代码如下: #include <iostream> using namespace std;   //将有二个有序数列a[first...mid]和a[mid...last]合并. void mergearray(int

  • C++选择排序算法实例

    选择排序 选择排序是一种简单直观的排序算法,它的工作原理如下.首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾.以此类推,直到所有元素均排序完毕. 选择排序的主要优点与数据移动有关.如果某个元素位于正确的最终位置上,则它不会被移动.选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换.在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常

  • C++实现各种排序算法类汇总

    C++可实现各种排序算法类,比如直接插入排序.折半插入排序.Shell排序.归并排序.简单选择排序.基数排序.对data数组中的元素进行希尔排序.冒泡排序.递归实现.堆排序.用数组实现的基数排序等. 具体代码如下: #ifndef SORT_H #define SORT_H #include <iostream> #include <queue> using namespace std; // 1.直接插入排序 template<class ElemType> void

随机推荐