首页 > 代码库 > 八大排序算法之---冒泡和选择
八大排序算法之---冒泡和选择
1.交换排序—冒泡排序（BubbleSort）
基本思想：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
算法分析：如果有n个数，则要进行n-1趟比较。在第1趟比较中要进行n-1次相邻元素的两两比较，在第j趟比较中要进行n-j次两两比较。比较的顺序从前往后，经过一趟比较后，将最值沉底（换到最后一个元素位置），最大值沉底为升序，最小值沉底为降序。
void bubbleSort(int a[], int n){
for(int i=0;i< n-1;++i){ /*外循环控制排序趟数，n个数排n-1趟*/
for(int j=0;j < n-i-1; j++){ /*内循环每趟比较的次数，第j趟比较n-j次，每次只将一个最大的数沉底*/
if(a[j] > a[j+1]){ /*相邻元素比较，逆序则交换*/
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
冒泡排序算法的改进：
对冒泡排序常见的改进方法是加入一标志性变量exchange，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。本文再提供以下两种改进算法：
1． 设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。
改进后算法如下:
void Bubble_1 ( int r[], int n) {
int i= n -1; //初始时,最后位置保持不变
while ( i> 0) {
int pos= 0; //每趟开始时,无记录交换
for (int j= 0; j< i; j++)
if (r[j]> r[j+1]) {
pos= j; //记录交换的位置
int temp = r[j];
r[j] = r[j+1];
r[j+1] = temp;
}
i= pos; //为下一趟排序作准备
}
}
算法分析：定义n-1次循环，每个数字比较n-j次，比较前一个数和后一个数的大小。然后交换顺序。
2．传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者), 从而使排序趟数几乎减少了一半。
改进后的算法实现为:
void Bubble_2 ( int r[], int n){
int low = 0;
int high= n -1; //设置变量的初始值
int tmp,j;
while (low < high) {
for (j= low; j< high; j++) //正向冒泡,找到最大者
if (r[j]> r[j+1]) {
tmp = r[j];
r[j] = r[j+1];
r[j+1] = tmp;
}
high--; //修改high值, 前移一位
for ( j=high; j>low; j++) //反向冒泡,找到最小者
if (r[j]<r[j-1]) {
tmp = r[j];
r[j] = r[j-1];
r[j-1] = tmp;
}
low++; //修改low值,后移一位
}
}
选择排序—简单选择排序（Simple Selection Sort）基本思想：在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。
简单选择排序的示例：
操作方法：在要排序的一组数中，选出最小的一个数与第一个位置的数交换； 然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。
第i趟，则从第i 个记录开始的n-i+1个记录中选出关键码最小的记录与第i 个记录交换，直到整个序列按关键码有序。
算法分析：每趟选出一个最值和无序序列的第一个数交换，n个数共选n-1趟。第i趟假设i为最值下标，然后将最值和i+1至最后一个数比较，找出最值的下标，若最值下标不为初设值，则将最值元素和下标为i的元素交换.
算法实现:
void select_sort(int *x, int n) { /*用指针来实现选择排序*/
int i, j, min, t;
for (i=0; i<n-1; i++) { /*要选择的次数:0~n-2共n-1次*/
min = i; /*假设当前下标为i的数最小,比较后再调整*/
for (j=i+1; j<n; j++) { /*循环找出最小的数的下标是哪个*/
if (*(x+j) < *(x+min)) {
min = j; /*如果后面的数比前面的小,则记下它的下标*/
}
}
if (min != i) { /*如果min在循环中改变了,就需要交换数据*/
t = *(x+i);
*(x+i) = *(x+min);
*(x+min) = t;
}
}
}
（2）核心代码：for(i=0;i<n-1;i++) { /*外循环控制趟数，n个数选n-1趟*/
k=i; /*假设当前趟的第一个数为最值,记在k中*/
for(j=i+1;j<n;j++) /*从下一个数到最后一个数之间找最值*/
if( a[k] < a[j]) /*若其后有比最值更大的*/
k=j; /*则将其下标记在k中*/
if( k != i) { /*若k不为最初的i值，说明在其后找到比其更大的数*/
t = a[k];
a[k] = a[i];
a[i] = t;
}
}
算法特点：每趟是选出一个最值确定其在结果序列中的位置，确定元素的位置是从前往后，而每趟最多进行一次交换，其余元素的相对位置不变。可进行降序排序或升序排序。
算法分析：定义外部n-1次循环，假设第一个为最值，放在参数中，在从下一个数以后找最值若后面有比前面假设的最值更大的就放在k中，然后在对k进行分析。若k部位最初的i值。也就是假设的i不是最值，那么就交换最值和当前序列的第一个数。。。。
八大排序算法之---冒泡和选择