算法与数据结构(二)附录:冒泡&插入&选择&am
2017-09-13 本文已影响213人
天涯明月笙
冒泡排序
冒泡排序(Bubble Sort),是一种 计算机科学领域的较简单的 排序算法。
它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端,故名。
算法原理:
冒泡排序算法的运作如下:(从后往前)
- 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
- 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤,除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
时间复杂度:
若文件的初始状态是正序的,一趟扫描即可完成排序。
所需的关键字比较次数C和记录移动次数M均达到最小值。
Cmin = n-1; Mmin = 0;
所以,冒泡排序最好的 时间复杂度为O(n)
若初始文件是反序的,需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值:
冒泡排序的最坏时间复杂度为
![](https://img.haomeiwen.com/i1779926/154fd33fb0c2ddf8.png)
综上,因此冒泡排序总的平均时间复杂度为O(n^2)
#include <iostream>
#include <algorithm>
#include "SortTestHelper.h"
#include "SelectionSort.h"
#include "InsertionSort.h"
using namespace std;
template<typename T>
void bubbleSort( T arr[] , int n){
bool swapped;//是否交换过
do{
swapped = false;//将交换过置为flase
for( int i = 1 ; i < n ; i ++ )
//从第二个位置开始循环。
//如果前一个位置的数大于后一个位置的数就让他交换。也就是往后浮
if( arr[i-1] > arr[i] ){
swap( arr[i-1] , arr[i] );
//往后浮了之后,置标志位为true。
swapped = true;
//true进入下一次循环。
}
// 优化, 每一趟Bubble Sort都将最大的元素放在了最后的位置
// 所以下一次排序, 最后的元素可以不再考虑
n --;
}while(swapped);//
}
int main() {
int n = 10000;
// Test for Random Array
cout<<"Test for Random Array, size = "<<n<<", randome range [0, "<<n<<"]"<<endl;
int *arr1 = SortTestHelper::generateRandomArray(n,0,n);
int *arr2 = SortTestHelper::copyIntArray(arr1, n);
int *arr3 = SortTestHelper::copyIntArray(arr1, n);
SortTestHelper::testSort("Selection Sort", selectionSort, arr1, n);
SortTestHelper::testSort("Insertion Sort", insertionSort, arr2, n);
SortTestHelper::testSort("Bubble Sort", bubbleSort, arr3, n);
delete[] arr1;
delete[] arr2;
delete[] arr3;
cout<<endl;
// Test for Random Nearly Ordered Array
int swapTimes = 100;
cout<<"Test for Random Nearly Ordered Array, size = "<<n<<", swap time = "<<swapTimes<<endl;
arr1 = SortTestHelper::generateNearlyOrderedArray(n, swapTimes);
arr2 = SortTestHelper::copyIntArray(arr1, n);
arr3 = SortTestHelper::copyIntArray(arr1, n);
SortTestHelper::testSort("Selection Sort", selectionSort, arr1, n);
SortTestHelper::testSort("Insertion Sort", insertionSort, arr2, n);
SortTestHelper::testSort("Bubble Sort", bubbleSort, arr3, n);
delete[] arr1;
delete[] arr2;
delete[] arr3;
return 0;
}
运行结果:
![](http://upload-images.jianshu.io/upload_images/1779926-8e2a66e2e5896de1.png)
可以看出在面对随机乱序的数组时,时间:冒泡排序>选择排序>插入排序
在面对几乎有序的数组时:冒泡>选择>插入
优化过的插入排序还是很棒的。
希尔排序:
#include <iostream>
#include "SortTestHelper.h"
#include "SelectionSort.h"
#include "InsertionSort.h"
#include "BubbleSort.h"
using namespace std;
template<typename T>
void shellSort(T arr[], int n){
int h = 1;
while( h < n/3 )
h = 3 * h + 1;
// 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093...
while( h >= 1 ){
// h-sort the array
for( int i = h ; i < n ; i ++ ){
// 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序
T e = arr[i];
int j;
for( j = i ; j >= h && e < arr[j-h] ; j -= h )
arr[j] = arr[j-h];
arr[j] = e;
}
h /= 3;
}
}
int main() {
int n = 10000;
// Test for Random Array
cout<<"Test for Random Array, size = "<<n<<", random range [0, "<<n<<"]"<<endl;
int *arr1 = SortTestHelper::generateRandomArray(n,0,n);
int *arr2 = SortTestHelper::copyIntArray(arr1, n);
int *arr3 = SortTestHelper::copyIntArray(arr1, n);
int *arr4 = SortTestHelper::copyIntArray(arr1, n);
SortTestHelper::testSort("Selection Sort", selectionSort, arr1, n);
SortTestHelper::testSort("Insertion Sort", insertionSort, arr2, n);
SortTestHelper::testSort("Bubble Sort", bubbleSort, arr3, n);
SortTestHelper::testSort("Shell Sort", shellSort, arr4, n);
delete[] arr1;
delete[] arr2;
delete[] arr3;
delete[] arr4;
cout<<endl;
// Test for Random Nearly Ordered Array
int swapTimes = 100;
cout<<"Test for Random Nearly Ordered Array, size = "<<n<<", swap time = "<<swapTimes<<endl;
arr1 = SortTestHelper::generateNearlyOrderedArray(n, swapTimes);
arr2 = SortTestHelper::copyIntArray(arr1, n);
arr3 = SortTestHelper::copyIntArray(arr1, n);
arr4 = SortTestHelper::copyIntArray(arr1, n);
SortTestHelper::testSort("Selection Sort", selectionSort, arr1, n);
SortTestHelper::testSort("Insertion Sort", insertionSort, arr2, n);
SortTestHelper::testSort("Bubble Sort", bubbleSort, arr3, n);
SortTestHelper::testSort("Shell Sort", shellSort, arr4, n);
delete[] arr1;
delete[] arr2;
delete[] arr3;
delete[] arr4;
return 0;
}
运行结果:
![](http://upload-images.jianshu.io/upload_images/1779926-88643792d62b9ace.png)
可以得出结论希尔排序属于基础排序算法里效果相当好的一个了。