首页 / C++ / C/C++ 知识点---排序实现

C/C++ 知识点---排序实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了C/C++ 知识点---排序实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3190字，纯文字阅读大概需要5分钟。

内容图文

1.冒泡排序
冒泡排序是O（N^2）复杂度的排序算法，效率较低，需要N趟遍历，每次将候选集中最小的数通过交换浮到最上面；
template <typename Type>
void BubbleSort(vector<Type> &arraySort, int lowIndex, int hightIndex)
{
bool bChange;
  for (int i=lowIndex; i<hightIndex; ++i)
  {
      bChange = false;
      for (int j=hightIndex; j>i; --j)
      {
          if (arraySort[j-1] > arraySort[j])
          {
              swap(arraySort[j-1], arraySort[j]);
              bChange = true;
          }
      }
      if (!bChange)
      {
          return;
      }
  }
}
2.选择排序
选择排序就是每次在候选集合中选择最小的数插入到候选结合的开头，并且不断的缩小候选集合的过程，从算法实现的角度讲，就是要进行N词遍历，每次在候选集合中选择最小的数放在候选集合前部的过程，并且不断的缩小候选集。
template <typename Type>
void SelectSort(vector<Type> &arraySort, int lowIndex, int hightIndex)
{
  Type tempMinIndex;
  for (int i=lowIndex; i<hightIndex; ++i)
  {
      tempMinIndex = i;
      for (int j=i+1; j<hightIndex; ++j)
      {
          if (arraySort[j] < arraySort[tempMinIndex])
          {
              tempMinIndex = j;
          }
      }
      if (tempMinIndex != i)
      {
          swap(arraySort[tempMinIndex], arraySort[i]);
      }
  }
}
3.插入排序
每次将一个数插入到有序的集合中，从算法实现的角度讲，就是进行N趟遍历，每次将第i个数插入到前面有序的集合中，最后达到有序。算法的复杂度为O（N^2），在实现时将第i个数与前面的i-1个数进行比较，如果小于就交换，最后插入到合适的位置。
template <tepename Type>
void InsertSort(vector<Type> &arraySort, int lowIndex, int hightIndex)
{
  for (int i=lowIndex+1; i<hightIndex; ++i)
  {
      Type tempValue = arraySort[i];
      j = i-1;
      while (j>=0 && temValue<arraySort[j])
      {
          arraySort[j+1] = arraySort[j];
          --j;
      }
      arraySort[j+1] = tempValue;
  }
}
4.快速排序
快速排序是最常用的也算是经典的排序算法，它是通过分治递归的方式实现，通过选取哨兵，并将元素与哨兵比较，按照大小将数组切分成两部分，并对这两部分按照同样的方式进行递归计算，最后达到有序。
template <typename Type>
void QuickSort(vector<Type> &arrarSort, int lowIndex, int hightIndex)
{
  int i = lowIndex;
  int j = hightIndex;
  Type tempValue = arraySort[lowIndex];
  while (i < j)
  {
      while (i<j && arraySort[j]>=tempValue)
      {
          j--;
      }
      if (i < j)
      {
          arraySort[i++] = arraySort[j];
      }
      while (i<j && arraySort[i]<tempValue)
      {
          i++;
      }
      if (i < j)
      {
          arraySort[j--] = arraySort[i];
      }
      QuickSort(arraySort, i+1, hightIndex);
      QuickSort(arraySort, lowIndex; i-1);
  }
  arraySort[i] = tempValue;
}
5.归并排序
归并排序也是用分治递归的思想进行求解，想将小块进行排序，然后合并来实现，归并排序的算法复杂度是O（N*logN），空间复杂度是O（N）
template <typename Type>
void Merge(vector<Type> &arraySort, int leftIndex, int midIndex, int rightIndex)
{
  int i = leftIndex;
  int j = midIndex+1;
  int n1 = midIndex-leftIndex+1;
  int n2 = rightIndex-midIndex;
  int k = 0;
  Type *tempArray = new Type[n1+n2];
  while (i<=midIndex && j<=rightIndex)
  {
      if (arraySort[i] < arraySort[j])
      {
          tempArray[k++] = arraySort[i++];
      }
      else
      {
          tempArray[k++] = arraySort[j++];
      }
  }
  while (i <= midIndex)
  {
      tempArray[k++] = arraySort[i++];
  }
  while (j <= rightIndex)
  {
      tempArray[k++] = arraySort[j++];
  }
  for (int i=0; i<n1; ++i)
  {
      arraySort[leftIndex++] = tempArray[i];
  }
  tempIndex = midIndex+1;
  for (int i=0; i<n2; ++i)
  {
      arraySort[tempIndex++] = tempArray[n1+i];
  }
  delete []tempArray;
}
template <typename Type>
void MergeSort(vector<Type> &arraySort, int leftIndex, int rightIndex)
{
  if (leftIndex < rightIndex)
  {
      int midIndex = (leftIndex+rightIndex)/2;
      MergeSort(arraySort, leftIndex, midIndex);
      MergeSort(arraySort, midIndex+1, rightIndex);
      Merge(arraySort, leftIndex, midIndex, rightIndex);
  }
}

原文：http://www.cnblogs.com/sz-leez/p/4482941.html

内容总结

以上是互联网集市为您收集整理的C/C++ 知识点---排序实现全部内容，希望文章能够帮你解决C/C++ 知识点---排序实现所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1305865.html

来源：【匿名】

【下一篇】c++有个库什么的吗?

更多 ►

【C/C++ 知识点---排序实现】教程文章相关的互联网学习教程文章

C/C++ 知识点---排序实现

C++基础知识总结----类的进阶知识点【代码】

还是那句话,我们继续在简单的代码中,体会学习C++,本节主要是体会学习类的进阶知识.一.构造函数与析构函数当创建一个对象时，往往需要做一些初始化工作，例如对数据成员赋值等。为了解决这个问题，C++提供了构造函数。构造函数（Constructor）是一种特殊的成员函数，它的名字和类名相同，没有返回值，不需要用户调用（用户也不能调用），而是在创建对象时自动执行。构造函数的作用是在创建对象时进行初始化工作，最常见的就...

C++primer知识点（一）【图】

一：g++c1.cpp -o c1.exe -std=c++11 c++11，加入了int a = {10}，的初始化形式，如果有精度损失，那么会有警告。二：对：const int引用= int //const 只是针对自己来说的错：int 引用 = constint //不符合逻辑与语法，引用不是常量，说明可以改，但引用的却是常量，矛盾了。三：引用的初始化（绑定）必须是类型一致：除了1：常量引用可以是，可转换成引用的类型的。因为是常量引用，既然不能改，编译器的实现方式是借助一个临...

C/C++知识点总结（5）【代码】【图】

运算符重载函数的限制：五个不能实现重载的符号：".", ".*", "::", "?", "sizeof"；重载运算符可以定义为类成员函数（这时候可以向当前对象发送消息的动作执行操作），也可定义为全局函数（一般为对应类的友元函数，此类函数需要显式指定所有参数，并且如果有转换构造函数，则可以使用于所有参数类型的运算）;一般的重载运算符函数可以被派生类继承使用，但是赋值运算符重载函数不能被继承；因此每一个派生类都最好定义自己的赋值运...

c++知识点总结-模板特化【代码】

类模板的全特化与偏特化类模板template<typename T1, typename T2> class Test { public:Test(T1 i,T2 j):a(i),b(j){cout<<"模板类"<<endl;} private:T1 a;T2 b; }; 全特化template<> class Test<int , char> { public:Test(int i, char j):a(i),b(j){cout<<"全特化"<<endl;} private:int a;char b; }; 偏特化template <typename T2> class Test<char, T2> { public:Test(char i, T2 j):a(i),b(j){cout<<"偏特化"<<endl;} private...

c++ namespace知识点

1. using 声明使用单个声明，比较安全；using编译指令导入全部，不安全。2.在名称空间中声明的名称的链接性为外部的。3.局部变量隐藏名称空间名和全局变量名，参看p328例；4.嵌套命名空间及命名空间的传递性，命名空间起别名；5. 同个名称空间是可以在头文件中写声明，在cpp中对应写实现；6. p334名称空间的注意事项9.3.4原文：https://www.cnblogs.com/liutianrui1/p/13352966.html

C++进阶知识点（2）

1.为函数的参数赋予默认值，如果给函数的某个参数设置了默认值，那么参数列表中该参数后面的所有参数都必须有默认值，调用函数的时候如果希望参数使用自己的默认值，只要不传入那个参数就可以了；void test5(int a,int b = 5,int c = 10,int d =15){ cout<<a+b+c+d<<endl;}int main(int argc,char *argv[]){ test5(5); test5(5,100);} 2.内联函数，在函数的返回类型前面加上inline就可以将这个函数声明为内联函数，声明为...

C++零散知识点【代码】

CString strDayofWeek = _T(""); 的意思 1.sComment是自定义的CString类型变量，代表什么意思自己说了算2._T是一个宏，作用是让你的程序支持Unicode编码。如果你的程序使用的是“多字节字符集”的话，他不起任何作用3._T("")表示把CString类型变量初始化为空。------------------------------------------------------------------------------原文：http://www.cnblogs.com/fclbky/p/4247909.html

C++的一些知识点汇总

数组形参数组形参void test(const int arr[]); //arr中的值不能被改变void test(const int *arr); //arr中的值不能被改变，包括arr[1]void test(int (&arr)[10]); //引用数组，10必须声明int &arr[10]; //引用数组，不能通过编译，下标操作符具有更高的优先级void test(int (*arr)[10]); //多维数组，int *arr[10]，指针数组void test(int arr[][10]); //多维数组原文：http://www.cnblogs.com/summerwinter/p/3634954.html

C++常见易忘知识点与常shi

vector的size和capacityreserve 与 resize 是区别的：reserve 用来给vector预分配存储区大小，即capacity的值，没有给这段内存进行初始化。reserve 的参数是推荐预分配内存的大小，实际分配的可能等于或大于这个值。这样做的好处就是消除当往vector插入数据时，size 超过原来的默认分配的capacity值时所带来的内存重分配开销。resize 不仅会改变vector的capacity大小，而且会重置size值，在C++ STL中，很多部分(目前包括set,...

C++ 01 基础知识点

1、为某一特定的问题而设计的指令序列称为：程序2、‘32位微型计算机’中的32位指的是：机器的字长3、存储设备中，存取速度最快的是：Cache4、指令的操作码表示的是：作何操作5、一条指令由哪两部分组成：操作码和地址码6、任何程序必须被加载到哪里中才能被CPU中执行：内存7、RAM:随机存储器：断电后会丢失存储的内容8、ROM：只读存储器：只能读取事先所存数据的固态半导体存储器，其中数据是由计算机制造厂预先写入的9、微型计算...

C++数据结构知识点【代码】【图】

数据结构(data stucture)的定义：数据结构由数据元素的集合和该集合中数据元素之间的关系组成。即{D,R}。线性结构，即线性表(linearlist). ---数组(array)，文件，栈(stack)，队列(queue)，优先级队列非线性结构 ---集合，图C++类默认访问级别是privatestruct默认访问级别是 public 这可以说是他们的惟一区别。union默认访问级别也是 public流是个简单的字符序列cout<<endl; 输出一个换行符，并清空流。C++的输入输出：void main...

《C++编程思想》第九章命名控制（知识点+习题+解答）【图】

一.相关知识点那些通常放在头文件里的名字，像常量、内联函数（inline function），在缺省情况下都是内部连接的（当然常量只有在C + +中缺省情况下是内部连接的，在 C中它缺省为外部连接）。注意连接只引用那些在连接/装载期间有地址的成员，因此类声明和局部变量并没有连接。名字空间的产生与一个类的产生非常相似： namespace MyLib{ //Declarations } 这就产生了一个新的名字空间,其中包含了各种声明.namespace与class、...

c++知识点【代码】

Static关键字1.1 C语言中的static的最主要功能是隐藏，其次因为static变量存放在静态存储区，所以它具备持久性和默认值01.2 C++中1）静态类数据成员无论建立多少个类的对象，都只有一个静态数据的拷贝。静态数据的初始化是在类外进行的。2）静态类函数它属于整个类，一般在静态成员函数中访问的基本上是静态数据成员或全局变量。 2. 友元2.1 友元函数在类中说明的某个函数不是该类的成员函数，可以访问该类的私有函数#include...

【转】C++易混知识点3. New Operator, Operator New, Placement New 实例分析,比较区别

我们知道，C++中引入了New 这个内置符号，很大方便了指针的使用，程序员不必关注与这块堆上新分配的内存是如何来的，如何初始化的，然后如何转换为我们想要的类型指针的。现在，我们重点来分析下这个NEW内置符号背后的步骤和所调用到的函数。这里面涉及到new operator， operator new， placement new.转载请注明出处： http://blog.csdn.net/elfprincexu1. New Operator (__type__ * a = new a();)C 语言当中，我们在新申请一块内...

首页 / C++ / C/C++ 知识点---排序实现

C/C++ 知识点---排序实现

内容导读

内容图文

内容总结

内容备注

内容手机端

【C/C++ 知识点---排序实现】教程文章相关的互联网学习教程文章

排序 - 相关标签

C++ - 技术教程分类

C++ - 最新教程

C++ - 最热教程