冒泡、选择和插入排序算法小结
冒泡排序:在排序的过程中总是小的数往前放,大数往后放,相当于气泡往上升(升序排列),所以称为冒泡排序。
思路:如果有 n 个数,则需要 n-1 趟比较(剩下一个数时不需要比较),在第一趟中进行n-1次两两比较,在第i趟需要进行n-i次两两比较,因此共需比较 (n-1)+(n-2)+...+(n-i)+...+1=n(n-1)/2 次。
<pre>
//冒泡法(升序排列)
int temp = 0; //中间变量
int sw = 0; //统计交换次数
int com = 0; //统计比较次数
for (int i = 0; i < N-1; i++){ //进行 N-1 趟比较
for (int j = 0; j < N-1 - i; j++){ //每趟中进行 N-i次比较
com++;
if (A[j] > A[j + 1]){ //相邻两个数进行比较
temp = A[j];
A[j] = A[j + 1];
A[j + 1] = temp; //交换相邻元素
//swap(A[j], A[j + 1]);
sw++;
}
}
}
cout << "\t比较次数为:" << com << endl;
cout << "\t交换次数为:" << sw << endl;
</pre>
结果:
稳定性:稳定排序是指数据中存在2个或者2个以上键值相等的元素时,这些元素在排序处理前后顺序不变。冒泡排序仅对数组中的相邻元素进行比较和置换,因此值相同的元素不会改变顺序,因此冒泡排序也属于一种稳定排序的算法。但是当比较条件改为
<pre>
A[j] >= A[j + 1]
</pre>
算法就会失去稳定性。
复杂度:假如数据总量为N,则冒泡排序需要进行N(N-1)/2次比较,也就是说冒泡排序在最换的情况下需要进行N(N-1)/2次比较运算,大多数时候,在计算复杂度时只留下对代数式影响最大的项,忽略常数项,因此算法的复杂度为O(N*N)。
PS:冒泡排序中的交换次数又称为反序数或逆序数,用来体现数据的错乱程度。
插入排序:插入排序就是依次取待排列数组的元素,将其插入到前面有序的数组中。它的工作原理可以用打扑克牌时排列手牌的方法类似:假如我现在要将手里的牌从小到大、从左到右进行排序,我需要将牌一张张抽出来,在前面I已排序的手牌中找到适当的位置进行插入,然后继续下一张。
思路:
<pre>
//按顺序输出数组元素
void trace(int A[], int N){
for (int i = 0; i < N; i++) {
if (i > 0)
cout << " "; //相邻元素之间输出一个空格
cout << A[i];
}
cout << endl;
}
/插入排序
void insertionSort(int A[], int N){
int j, i, v;
for (i = 1; i < N; i++){
v = A[i];
j = i - 1;
while (j >= 0 && A[j]>v){
A[j + 1] = A[j];
j--;
}
A[j + 1] = v;
cout << "\t\t ";
trace(A, N);
}
}
</pre>
外层循环i从1开始自增,在每次循环开始,将A[i]的值临时保存在临时变量v中,内部循环是从已排序部分找出比v大的元素并让它们顺序后移一个位置。这里让j从i-1开始向前自减,同时将比v大的元素从A[j]移动到A[j+1],一旦j等于-1或者当前A[j]小于等于v则结束循环,并将v插入到当前j+1的位置。
结果:
稳定性:在排序中只将比v大的元素向后平移,不相邻元素不会直接交换换位置,因此该算法是稳定排序算法。
复杂度:这里需要估算每个i循环中A[j]元素向后移动的次数,最坏情况下,每个i循环都需要执行i次移动,总共需要1+2+...+N-1=N(N-1)/2次移动,即复杂度为O(N2)。
PS:对于插入排序,输入数据的顺序能大幅影响它的复杂度,上面说的它的复杂度为O(N2)也仅仅指输入排序为降序排列的情况,如果输入数据为升序排列,那么A[j]从头到尾都不需要移动,只需经历N-1次比较便可执行完毕,因此插入排序的优势在于能快速处理相对有序的数据。
选择排序:从需要排序的数据中选择最小的值和第一个交换,再从剩下的部分选取最小的值和第二个进行交换,循环执行下去,最后完成数据的排序。
思路:
<pre>
//选择排序算法
int selectionSort(int A[], int N){
int i, j, t, minj, sw = 0;
for ( i = 0; i < N-1; i++ )
{
minj = i;
for( j = i+1; j < N; j++ )
{
if (A[j] < A[minj]) minj = j;
}
t = A[i]; A[i] = A[minj]; A[minj] = t;
if( i != minj ) sw++;
}
return sw;
}
</pre>
在每一轮i的循环中,通过j自增来遍历A[i]到A[N-1],从而确定minj,确定minj后,让起始元素A[i]与最小值元素A[minj]进行交换。
结果:
稳定性:由于选择排序会直接交换两个不相邻的元素,所以属于不稳定的排序算法。
复杂度:假设数据总数为N,那么无论在任何情况下,都需要进行(N-1)+(N-2)+...+1=N(N-1)/2次比较运算,用于搜索未排序部分的最小值。因此算法的复杂度为O(N2)。
总结:冒泡排序法与选择排序相比,一个从局部入手减少逆序元素,一个放眼大局逐个选择最小值,两者思路不同,但是它们都有着“通过i次外层循环,从数据中顺序求出i个最小值”的相同特征。相对地,插入排序是通过i次外层循环,直接将原数组的i个元素重新排序。另外冒泡排序和选择排序不依赖数据,即比较运算次数(算法负责度)不受输入数据影响,而插入算法在执行时依赖数据,处理某些数据时具有很高的效率。
推荐阅读
-
贪婪算法在 Python、JavaScript、Java、C++ 和 C# 中的多种实现及其在硬币变化、分数骑士、活动选择和使用哈夫曼编码的最小生成树问题中的应用实例
-
经典排序算法和 python 详情(II):冒泡排序、双向冒泡排序、插入排序和希尔排序
-
通过冒泡排序和选择_c 语言数组对 10 个整数从大到小进行排序 冒泡排序
-
数据结构与算法(III)--简单排序算法[冒泡、选择、插入排序算法]
-
气泡排序(超级详细)--升序",从小到大;另一种是 "降序",从大到小。该主题可抽象为 "按升序对 n 个数字排序 "的一般形式。 排序是一种重要的基本算法。排序的方法有很多种,但在本题中我们将使用冒泡排序法。 冒泡法的基本思想 冒泡法的基本思想是,每次比较相邻的两个数字时,较小的那个会被移到前面。如果有 5 个数字9,8,5,2,0,第一次将前两个数字 8 和 9 互换。第二次将第二个和第三个数字(9 和 5)对调......这样一共对调 4 次,得到 8-5-2-0-9 的顺序,可以看到:最大的数字 9 一直在 "下沉",成为最下面的一个数字,而小的数字 "上升" 最小的数字 "上升"。最小的数字 0 已经向上 "浮 "了一个位置。经过第一次比较(共 4 次比较和交换),得到了最大的数字 9。 然后进行第二趟比较,对剩下的前 4 个数字(8、5、2、0)进行新一轮比较,这样第二个最大的数字就 "沉到了底部"。同样,按照上述方法进行第二轮比较。经过 3 次比较和交换,我们得到了第二大数 8。 按照这个规律,我们可以推断出,比较 5 个数字需要 4 次旅行,才能将 5 个数字从小到大排列起来。在第一次旅行中,两个数字之间进行了 4 次比较,在第二次旅行中,进行了 3 次比较......在第四次旅行中,只进行了一次比较。 思路总结 总结:如果有 n 个数字,那么要进行 n-1 次比较。在第一次行程中进行 n-1 次比较,在第 i 次行程中进行 n-i 次比较。
-
JAVA 冒泡排序算法(包括详细的过程代码解释和优化)"推荐收藏"。
-
排序算法:冒泡排序、插入排序、选择排序、希尔排序
-
十大排序算法讲解(一)气泡排序、选择排序、插入排序、快速排序、希尔排序 [简单易懂]
-
三种基本排序算法(气泡排序、选择排序、插入排序)
-
JAVA 冒泡排序算法(附详细过程代码解释和优化)