大家好，又见面了，我是全栈君，祝每个程序员都可以多学几门语言。
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;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/118111.html原文链接：https://javaforall.net
