c++之数据排序

~ 信息获取后通常需要进行处理，处理后的信息其目的是便于人们的应用。信息处理方法有多种，通常有数据的排序、查找、插入、删除、归并等操作。
选择排序
（1） 基本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在待排序的数列的最前，直到全部待排序的数据元素排完。（2）排序过程： 【示例】： 初 始 关键字 [49 38 65 97 76 13 27 49]第一趟排序后 13［38 65 97 76 49 27 49］第二趟排序后 13 27［65 97 76 49 38 49］第三趟排序后 13 27 38 [97 76 49 65 49]第四趟排序后 13 27 38 49 [76 97 65 49]第五趟排序后 13 27 38 49 49 [97 65 76]第六趟排序后 13 27 38 49 49 65 [97 76]第七趟排序后 13 27 38 49 49 65 76 [97]最后排序结果 13 27 38 49 49 65 76 97

冒泡排序
（1）基本的冒泡排序 ①基本思想 依次比较相邻的两个数，把大的放前面，小的放后面。即首先比较第1个数和第2个数，大数放前,小数放后。然后比较第2个数和第3个数......直到比较最后两个数。第一趟结束，最小的一定沉到最后。重复上过程,仍从第1个数开始,到最后第2个数，然后...... 由于在排序过程中总是大数往前，小数往后，相当气泡上升，所以叫冒泡排序。 下面是6个元素的排序的过程 4 5 7 1 2 3 ┗━━┛ 5 4 7 1 2 3 ┗━━┛ 5 7 4 1 2 3 ┗━━┛ 5 7 4 1 2 3 ┗━━┛ 5 7 4 2 1  3 ┗━━┛ 第一趟结束 5 7 4 2 3 ① ┗━━┛ 7 5 4 2 3 1 ┗━━┛ 7 5 4 2 3 1 ┗━━┛ 7 5 4 2 3 1 ┗━━┛ 第二趟结束 7 5 4 3 ② 1 ┗━━┛ 7 5 4 3 2 1 ┗━━┛ 7 5 4 3 2 1 ┗━━┛ 第三趟结束 7 5 4 ③ 2 1 ┗━━┛ 7 5 4 3 2 1 ┗━━┛  第四趟结束 7 5 ④ 3 2 1 ┗━━┛ 第五趟结束 ⑦ ⑤ 4 3 2 1 ②算法实现
（2）改进 上例中，可以发现，第二趟结束已经排好序。但是计算机此时并不知道已经排好序。所以，还需进行一次比较，如果没有发生任何数据交换，则知道已经排好序，可以不干了。因此第三趟比较还需进行，第四趟、第五趟比较则不必要。 我们设置一个布尔变量bo 来记录是否有进行交换。值为false表示本趟中进行了交换，true 则没有。代码如下:

桶排序
桶排序的思想是若待排序的记录的关键字在一个明显有限范围内(整型)时，可设计有限个有序桶，每个桶装入一个值（当然也可以装入若干个值），顺序输出各桶的值，将得到有序的序列。 例：输入n个0到100之间的不相同整数，由小到大排序输出。

插入排序
插入排序是一种简单的排序方法，其算法的基本思想是： 假设待排序的数据存放在数组R[1..n]中，增加一个哨兵结点x。 (1) R[1]自成1个有序区，无序区为R[2..n];(2) 从i=2起直至i=n为止，将R[i]放在恰当的位置，使R[1..i]数据序列有序; ① x:=R[i]; ② 将x与前i-1个数比较 , j:=i-1; while xa[j] do j:=j-1; ③ 将R数组的元素从j位置开始向后移动: for k:=i downto j do a[k]:=a[k-1]; ④ R[j]=x; (3) 生成包含n个数据的有序区。. 例如:设n=8，数组R中8个元素是: 36,25,48,12,65,43,20,58，执行插入排序程序后，其数据变动情况： 第0步:[36] 25 48 12 65 43 20 58第1步:[25 36] 48 12 65 43 20 58第2步:[25 36 48] 12 65 43 20 58第3步:[12 25 36 48] 65 43 20 58第4步:[12 25 36 48 65] 43 20 58第5步:[12 25 36 43 48 65] 20 58第6步:[12 20 25 36 43 48 65] 58第7步:[12 20 25 36 43 48 58 65] 其算法的时间复杂性为O(n2)插入排序适用于原先数据已经排列好，插入一个新数据的情况。

快速排序
快速排序是对冒泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 假设待排序的序列为{a[L],a[L+1],a[L+2],……,a[R]}，首先任意选取一个记录（通常可选中间一个记作为枢轴或支点），然后重新排列其余记录，将所有关键字小于它的记录都放在左子序列中，所有关键字大于它的记录都放在右子序列中。由此可以将该“支点”记录所在的位置mid作分界线，将序列分割成两个子序列和。这个过程称作一趟快速排序（或一次划分）。 一趟快速排序的具体做法是：附设两个指针i和j，它们的初值分别为L和R，设枢轴记录取mid，则首先从j所指位置起向前搜索找到第一个关键字小于的mid的记录，然后从i所指位置起向后搜索，找到第一个关键字大于mid的记录，将它们互相交换，重复这两步直至ij为止。 快速排序的时间的复杂性是O(nlog2n)，速度快,但它是不稳定的排序方法。就平均时间而言，快速排序是目前被认为是最好的一种内部排序方法 由以上讨论可知，从时间上看，快速排序的平均性能优于前面讨论过的各种排序方法，但快速排序需一个栈空间来实现递归。若每一趟排序都将记录序列均匀地分割成长度相接近的两个子序列，则栈的最大深度为log(n+1)。

归并排序
将两个或两个以上有序的数列(或有序表)，合并成一个仍然有序的数列(有序表)，这种操作称为归并操作。这样的方法经常用于多个有序的数据文件归并成一个有序的数据文件。若将两个有序表合并成一个有序表则称为二路归并，同理，有三路归并、四路归并等。二路归并比较简单，所以我们只讨论二路归并。例如有两个有序表: (7，10，13，15)和(4，8，19，20)，归并后得到的有序表为: (4，7，8，10，13，15，19，20)。 归并过程为:比较A[i]和A[j]的大小，若A[i]≤A[j]，则将第一个有序表中的元素A[i]复制到R[k]中，并令i和k分别加1，即使之分别指问后一单元，否则将第二个有序表中的元素A[j]复制到R[k]中，并令j和k分别加1;如此循环下去，直到其中的一个有序表取完,然后再将另一个有序表中剩余的元素复制到R中从下标k到下标t的单元. 二路归并算法描述为(A[s,t]中的数据由小到大合并到R[s,t]中):

归并排序(Merge sort)就是利用归并操作把一个无序表排列成一个有序表的过程。二路归并排序的过程是首先把待排序区间（即无序表）中的每一个元素都看作为一个有序表，则n个元素构成n个有序表，接着两两归并（即第一个表同第二个表归并，第三个表同第四个表归并，…），得到[n/2]个长度为2的有序表（最后一个表的长度可能小于2），称此为一趟归并，然后再两两有序表归并，得到[[n/2]/2]个长度为4的有序表（最后一个表的长度可能小于4），如此进行下去，直到归并第[log2n]趟后得到一个长度为n的有序表为止。 归并排序算法我们用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。对左右子区间的排序与原问题一样，所以我们可以调用同样的子程序，只是区间大小不一样。

各种排序算法的比较
1.稳定性比较 插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的。 选择排序、希尔排序、快速排序、堆排序是不稳定的。
2.时间复杂性比较 插入排序、冒泡排序、选择排序的时间复杂性为O(n2)；快速排序、堆排序、归并排序的时间复杂性为O(nlog2n)；桶排序的时间复杂性为O(n); 若从最好情况考虑，则直接插入排序和冒泡排序的时间复杂度最好，为O(n)，其它算法的最好情况同平均情况相同；若从最坏情况考虑，则快速排序的时间复杂度为O(n2)，直接插入排序和冒泡排序虽然平均情况相同，但系数大约增加一倍，所以运行速度将降低一半，最坏情况对直接选择排序、堆排序和归并排序影响不大。 由此可知，在最好情况下，直接插入排序和冒泡排序最快；在平均情况下，快速排序最快；在最坏情况下，堆排序和归并排序最快。
3.辅助空间的比较 桶排序、二路归并排序的辅助空间为O(n)，快速排序的辅助空间为O(log2n)，最坏情况为O(n)，其它排序的辅助空间为O(1);
4.其它比较 插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。反而在这种情况下，快速排序反而慢了。 当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。 若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排序。 当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。 当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序

---

和龙市18272888184： C++怎样实现数的排序 - ？
江花济诺： 把数存在数组中,然后把小的放在前面,大的放在后面. 那么就有很多种方法了. 1找小的放前面,第二个以后和第一个比小了就交换位置.也可以从最后一个开始找大的放后面. 2两头同时进行,鸡尾酒排序. 3快速排序,算法中有的. 其他排序要涉及一些稍微男的数据结构..

和龙市18272888184： C++中怎么对数据进行排序 - ？
江花济诺： 写入文件之前就排好,用algorithm的sort函数 给你写个 bool compare(student& s1, student& s2) { return s1.学号 < s2.学号; // 改成大于是从大到小排 } 然后对一个student数组 const int N=3; student n[N]; sort(n,n+N,compare);

和龙市18272888184： C++数组排序有哪几种算法? - ？
江花济诺： 插入排序算法1.从有序数列和无序数列{a2,a3,…,an}开始进行排序;2.处理第i个元素时(i=2,3,…,n) , 数列{a1,a2,…,ai-1}是已有序的,而数列{ai,ai+1,…,an}是无序的.用ai与ai-1,a i-2,…,a1进行比较,找出合适的位置将ai插入;3.重复第二...

和龙市18272888184： c++几种常见的排序程序 - ？
江花济诺： (1)“冒泡法” 冒泡法大家都较熟悉.其原理为从a[0]开始,依次将其和后面的元素比较,若a[0]>a[i],则交换它们,一直比较到a[n].同理对a[1],a[2],...a[n-1]处理,即完成排序.下面列出其代码:void bubble(int *a,int n) /*定义两个参数:数组首地...

和龙市18272888184： c++快速排序法 - ？
江花济诺： int qpass(RecordYype r[],int left,int right)/*对记录数组r中的r[left]至r[right]部分进行一趟排序,并得到枢轴的位置,使得排序后的结果满足期之后(前)的记录的关键字均不小于(大于)枢轴记录*/ { x=r[left]; low=left; high=right; while(low<high) { ...

和龙市18272888184： 用C++ 编写一个排序函数,用选择法对一批整数按从大到小的次序进行排序. - ？
江花济诺： //一批整数选择法降序排列#include<iostream>#include<vector> using namespace std; void to_sort(vector<int> s) { int temp; for(vector<int>::size_type ix = 0;ix != s.size()-1;ix++) for(vector<int>::size_type j = ix+1;j != s.size();j++) if(s.at(ix)<s.at(j)) { ...

和龙市18272888184： c++排序函数 - ？
江花济诺： #include int *p(int x[],int y) { int i,j,a; for(i=0;i<y...

和龙市18272888184： C++排序,随便输入十个数据,让他们按从小到大或大到小的顺序自动排列出来; - ？
江花济诺： 最简单的,简单插入排序,在你输入数据的同时就完成排序了........,从头比到尾,小的放前,大的放后,中间的插入....

和龙市18272888184： 在C++中数组的排序方法有哪些? - ？
江花济诺： 大体上可以分为四类:插入排序,选择排序和交换排序; 插入排序有:直接插入排序,希尔排序; 选择排序有:直接选择排序,堆排序 交换排序有:冒泡排序,快速排序 如果数组比较大的话也可用归并排序,效率比较高 各种排序方法各有所长,有的效率比较高,有的空间消耗比较小,总的来说,要针对不同的问题选择合适的方法; 另外,我有各种排序的源代码需要的话留下邮箱.是我以前学的时候写的!

和龙市18272888184： 用c++语言将十个数排序？
江花济诺： #include ＂stdio.h＂ #include ＂conio.h＂ int a[1000]; int num[1000]; int main(void) { int n=10,i,j,k,tmp; for(i=0;i&lt;n;i++)scanf(＂%d＂,&amp;num[i]); for(i=0;i&lt;n;i++)//选择排序 { k=i; for(j=i+1;j&lt;n;j++) { if(num[j]&gt;num[k])k=j; } tmp=num[i]; num[i]=...