排序算法概述
所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。
排序算法根据是否需要访问外存分为内部排序和外部排序。
内部排序是指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。
外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。
冒泡排序
冒泡排序的效率很低，但是算法实现起来很简单，因此很适合作为研究排序的入门算法。
基本思想
对当前还未排好序的范围内的全部数，自上而下对相邻的俩个数依次进行比较和调整，让较大的数下沉，较小的数往上冒。即：每当俩相邻的数比较后发现他们的排序与排序的要求相反时，就将他们交换。每次遍历都可确定一个最大值放到待排数组的末尾，下次遍历，对该最大值以及它之后的元素不再排序（已经排好）。
public void maoPao(int[] array){
int temp;
int len = array.length;
for(int i=0;i<len-1;i++){ //外层循环：每循环一次就确定了一个相对最大元素
for(int j=1;j<len-i;j++){ //内层循环：有i个元素已经排好，根据i确定本次的比较次数
if(array[j-1]>array[j]){ //如果前一位大于后一位，交换位置
temp = array[j-1];
array[j-1] = array[j];
array[j] = temp;
}
}
}
}算法分析
如果待排数组中一共有7个数，第一轮排序时进行了6次比较，第二轮排序时进行了5比较，依次类推，最后一轮进行了一次比较。
加入元素总数为N，则一共需要的比较次数为：
(N-1)+ (N-2)+ (N-3)+ ...1=N*(N-1)/2
这样，算法约做了N2/2次比较。因为只有在前面的元素比后面的元素大时才交换数据，所以交换的次数少于比较的次数。如果数据是随机的，大概有一半数据需要交换，则交换的次数为N2/4（不过在最坏情况下，即初始数据逆序时，每次比较都需要交换）。
交换和比较的操作次数都与N2成正比，由于在大O表示法中，常数忽略不计，冒泡排序的时间复杂度为O(N2)。
O(N2)的时间复杂度是一个比较糟糕的结果，尤其在数据量很大的情况下。所以冒泡排序通常不会用于实际应用。
冒泡排序的改进
冒泡排序的效率比较低，所以我们要通过各种方法改进。
最简单的改进方法是加入一标志性变量，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程;
对于算法来说，没有最好，只有更好。传统的冒泡算法每次排序只确定了最大值，我们可以在每次循环之中进行正反两次冒泡，分别找到最大值和最小值，如此可使排序的轮数减少一半。
改进代码如下：
public void maoPao2(int[] array){
long count = 0; //循环次数
if(null == array)
return;
int low = 0;
int high = array.length - 1;
int temp; //临时变量
while (low < high){
//正向冒泡 选出最大的
for (int i=low; i<high; i++){
if (array[i] > array[i+1]){ //如果前一位大于后一位，交换位置
temp = array[i+1];
array[i+1] = array[i];
array[i] = temp;
}
count++;
}
high--;
//反向冒泡 选出最小的
for(int i=high; i>low; i--){
if(array[i] < array[i-1]){ //如果后一位小于前一位，交换位置
temp = array[i-1];
array[i-1] = array[i];
array[i] = temp;
}
count++;
}
low++;
}
}效率分析
少量数据
public static void main(String[] args){
PaiXu paiXu = new PaiXu();
int[] array = {4,2,7,1,9,6,3,8,5};
long start = System.currentTimeMillis();
paiXu.maoPao(array.clone());
long end = System.currentTimeMillis();
System.out.println("********maoPao排序完成************用时:" + (end - start));
long start2 = System.currentTimeMillis();
paiXu.maoPao2(array.clone());
long end2 = System.currentTimeMillis();
System.out.println("********maoPao2排序完成************用时:" + (end2 - start2));
}结果:
1 2 3 4 5 6 7 8 9
********maoPao排序完成************用时:0
1 2 3 4 5 6 7 8 9
********maoPao2排序完成************用时:0
大量数据
/**
*创建一个数据
*
*/
public int[] newArr(){
int[] arr = new int[100000]; //构建一个空的一维数组
for(int i=0;i<arr.length;i++){
int temp = (int)(Math.random()*100000)+1;//随机产生一个 1~10 的整数
arr[i] = temp;//将产生的数添加到数组
}
return arr;
}
public static void main(String[] args){
PaiXu paiXu = new PaiXu();
int[] array = paiXu.newArr();
long start = System.currentTimeMillis();
paiXu.maoPao(array.clone());
long end = System.currentTimeMillis();
System.out.println("********maoPao排序完成************用时:" + (end - start));
long start2 = System.currentTimeMillis();
paiXu.maoPao2(array.clone());
long end2 = System.currentTimeMillis();
System.out.println("********maoPao2排序完成************用时:" + (end2 - start2));
}结果:
1 4 7 8 8 8 9 9 10 11 13 15 15 15 16 17 18 19 19 20 22 24 26 27 29 29 31 32 34 35
********maoPao排序完成************用时:18709
1 4 7 8 8 8 9 9 10 11 13 15 15 15 16 17 18 19 19 20 22 24 26 27 29 29 31 32 34 35
********maoPao2排序完成************用时:12633
网友评论