各类算法与性能分析
排序算法概论
1.冒泡排序O(n2 )：
public class BubbleSort{
public static int[] sort (int[] array){
if(array.length == 0){
return array;
}
for(int i=0;i<array.length;i++){
for(int j=0;j<array.length-1-i;j++){
if(array[j+1]<array[j]){
int temp = array[j+1];
array[j+1] = array[j];
array[j] = temp;
}
}
}
}
}
2.简单选择排序O(n2)
冒泡排序的优化
public class ChoiceSort{
public static int[] sort(int[] array){
if (array.length == 0)
return array;
for(int i=0;i<array.length;i++){
//存放最小数的下标
int minIndex = i;
for(int j=i;j<array.length;j++){
//找到最小的那个数
if(array[j]<array[minIndex]){
minIndex = j;
}
}
//交换
int temp = array[minIndex];
array[minIndex] = array[i];
array[i] = temp;
}
}
}
3.简单插入排序O(n2)
插入排序当前数据向后移动一位不会覆盖下一位的元素吗?
不会 比较一个移动一个，移动前后一个位置已经空出来了。
public class InstertionSort {
public static int[] sort(int[] array){
if (array.length == 0)
return array;
int currentValue;//待排序的数据
for(int i=0;i<array.length-1;i++){//默认第一个元素已经排序
int preIndex = i;//已排序数据的索引
currentValue = array[preIndex+1];
while(preIndex >= 0 && currentValue < array[preIndex]){
array[preIndex+1] = array[preIndex];
preIndex--;//遍历已排序的数组
}
array[preIndex+1] = currentValue;
}
}
}
4.分治法
1.希尔排序O(nlogn)
改进了简单插入排序，也称为缩小增量排序，突破了O(n2)
public class ShellSort{
public static int[] sort(int[] array){
if(array.length == 0)
return array;
}
int len = array.length;
int grap = len/2;
//组内待排序的数据
int currentValue;
while(grap>0){
for(int i=grap;i<len;i++)
currentValue = array[i];
int preIndex = i-grap;
while(preIndex>0&&array[preIndex]>currentValue){
array[preIndex + grap] = array[preindex];
preIndex = preIndex - grap;
}
}
grap = grap/2;
}
2.归并排序O(nlogn)
public class MergeSort{
public static int[] sort(int[] array){
//切分的位置
int mid = array.length/2;
int[] left = Arrays.copyOfRange(array,0,mid);
int[] right = Arrays.copyOfRange(array,mid,array.length)
return merge(sort(left),sort(right));
private static int[] merge(int[] left, int[] right){
int[] result = new int[left.length + right.length];
for(int index = 0.leftIndex = 0.rightIndex = 0;index<result.length;index++){
if(leftIndex>=left.length){
result[index] = right[rightIndex++]
}
else if(rightIndex>=right.length){
result[index] = left[rightIndex++]
}
else if(left[leftIndex]>=right.length){
result[index] = right[rightIndex++]
}
else{
result[index] = left[leftIndex++]
}
}
}
3.快速排序O(nlogn)
20世纪科学和工程十大算法
