浅谈算法--排序

我们工作时候处理数据时候会遇到一些处理数据排序的问题。这里我说两种比较常用的方法：一、冒泡排序法。二、归并排序法。

 

首先来说一下 冒泡排序法：这个方法大家应该还是比较熟悉的。核心思想是下面的一段代码——————

for（int i=1;i<list.length;i++）{

for(int j=0;j<list.lenght-i;j++){

if(list[j]>list[j+1]){

swap list[j] with list[j++]

}

}

}

 

这是核心代码段，思想就是从数组的第一个数据开始和后面比较小的不动，大的后移。直到循环结束。有时候会觉得这个比较耗时间的，其实我们可以稍微的改进一下，在某些情况下会提高不少效率。例子如下：

/*
冒泡排序法
*/
public class BubbleSort
{
public static void main(String[] args)
{
//System.out.println("Hello World!");
int[] list = {7,4,8,2,5,9,-1,38,3};
bubbleSort(list);
for(int i=0;i<list.length;i++){
System.out.println(list[i]);
}
}

public static void bubbleSort(int[] list){
boolean needNextPass = true;
for(int i = 1;i< list.length && needNextPass;i++){
for(int j=0;j<list.length-i;j++){
if(list[j]>list[j+1]){
int tmp = list[j];
list[j] = list[j+1];
list[j+1] = tmp;
needNextPass = true;
}

}
}
}

}

 

上面的这个例子只是加一个参数来判断，但是由于这个参数，会在大多数的情况下，使程序的效率大大的提高了。

 

然后我们来说一下一个大家可能不是很熟悉的 归并排序法。核心思想就是二分法：

具体代码如下

/*
归并排序
*/
public class MergeSort
{
public static void main(String[] args)
{
int[] list = {2,3,2,5,6,1,-2,3,14,12};
mergeSort(list);
for(int i=0;i<list.length;i++){
System.out.print(list[i]+" ");
}

}
//迭代分组
public static void mergeSort(int[] list){
if(list.length>1){
int[] firstHalf = new int[list.length/2];
System.arraycopy(list,0,firstHalf,0,list.length/2);
mergeSort(firstHalf);

int secondHalfLength = list.length - list.length/2;
int[] secondHalf = new int[secondHalfLength];
System.arraycopy(list,list.length/2,secondHalf,0,secondHalfLength);
mergeSort(secondHalf);

int[] temp = merge(firstHalf,secondHalf);
System.arraycopy(temp,0,list,0,temp.length);
}
}
//合并数组
public static int[] merge(int[] list1,int[]list2){
int[] temp = new int[list1.length+list2.length];

int current1 = 0;
int current2 = 0;
int current3 = 0;

while(current1<list1.length && current2<list2.length){
if(list1[current1]<list2[current2]){
temp[current3++] = list1[current1++];
}else{
temp[current3++] = list2[current2++];
}
}

while(current1<list1.length){
temp[current3++] = list1[current1++];
}
while(current2<list2.length){
temp[current3++] = list2[current2++];
}

return temp;
}

}

 

效率的话 我就简单的将结果说一下，因为具体测试效率是有一套测试的，具体可以自己去网上找找；

 

归并的效率高于冒泡的效率。