排序算法之从冒泡排序所想到的

/*
 * bubblesort.cpp
 *
 *  Created on: 2014年5月17日
 *      Author: pc
 */


#include 
#include 
#include 

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  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  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  arr[j]){
				swap3(arr,j-1,j);
				flag = j;//对方式2的改进...用来标记发生交换的是哪一个位置
			}
		}
	}
}

void createReverseArr(){
	int i = 0;
	for(i = 0 ; i