首页 > 代码库 > 排序算法之从冒泡排序所想到的
排序算法之从冒泡排序所想到的
1、算法思想描写叙述:
1)将相邻的两个数进行比較,假设前面的一个大于后面的一个,则将他们交换。每次循环能使一个数达到有序状态。
2、时间复杂度:
平均O(n^2)。最佳:O(n),在序列一開始就是正序的时候取得
3、实现及优化。
下面给出三种实现方式
/* * bubblesort.cpp * * Created on: 2014年5月17日 * Author: pc */ #include <iostream> #include <cstdio> #include <ctime> using namespace std; const int maxn = 10; int arr[maxn]; /** * 第一种交换算法: * 借助中间变量 */ void swap1(int arr[],int i,int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } /** * 另外一种交换算法: * 不借助中间变量,使用算术运算 */ void swap2(int arr[],int i, int j){ arr[i] = arr[i] + arr[j]; arr[j] = arr[i] - arr[j]; arr[i] = arr[i] - arr[j]; } /** * 第三种交换算法: * 使用位运算 */ void swap3(int arr[], int i, int j){ arr[i] = arr[i]^arr[j]; arr[j] = arr[i]^arr[j]; arr[i] = arr[i]^arr[j]; } /** * 冒泡排序的第一种方式: * 标准方式 */ void bubblesort1(int arr[],int n){ int i; int j; for(i = 0 ; i < n ;++i){//循环n-1次,每次能是一个数达到有序状态 for(j = 0 ; j < n-i-1 ; ++j){//每次将从第一个数到有序状态之前的数进行比較(有序状态以后的数不再须要进行比較) if(arr[j] > arr[j+1]){//假设前面的数大于后面的数 swap3(arr,j,j+1);//则进行交换 } } } } /** * 冒泡排序的另外一种方式:採用"扫描一遍以后,假如没有发生交换,即是达到了有序状态"的特点进行优化 */ void bubblesort2(int arr[],int n){ int k = n; bool flag = true; while(flag){ flag = false; for(int j = 0 ; j < k-1 ; ++j){ if(arr[j] > arr[j+1]){ swap3(arr,j,j+1); flag = true;//用来标记这一次是否发生了交换 } } --k; } } /** * 冒泡排序的第三种方式:在另外一种的基础上,用于处理"假如有100个数据,假如后90个都已经有序的情况" */ void bubblesort3(int arr[],int n){ int k; int flag = n; while(flag > 0){ k = flag; flag = 0; for(int j = 1 ; j < k ; ++j){ if(arr[j-1] > arr[j]){ swap3(arr,j-1,j); flag = j;//对方式2的改进...用来标记发生交换的是哪一个位置 } } } } void createReverseArr(){ int i = 0; for(i = 0 ; i < maxn ; ++i){ arr[i] = maxn - i; } } void printArr(){ int i; for(i = 0 ; i < maxn ; ++i){ printf("%d " , arr[i]); } printf("\n"); } time_t printTime(string str){ time_t now = time(NULL); cout << str <<": "<<now <<endl; return now; } /** * 获取系统当前时间 */ time_t getTime(){ time_t now = time(NULL); return now; } int main(){ createReverseArr(); printArr(); time_t before = getTime(); bubblesort3(arr,maxn); time_t after = getTime(); printArr(); cout<< "cost: "<<after - before <<"s"<<endl; }
排序算法之从冒泡排序所想到的
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。