排序算法

一. 冒泡排序

基本思想：比较大小
实现思路：将数大的下沉，小的数冒起。
伪代码：

for(i=0;i<n-1;i++){
    for(j=0;j<n-1-i;j++){
        if(a[j]>a[i]){
        //交换a[j]和a[i]
        }
    }
}

最坏时间复杂度：O(n^2)

二. 插入排序

基本思想：在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

伪代码：

public void insertSort(int[]list){
    for(int i=0;i<list.lenght-1;i++){
        for(int j=i+1;j>0;j--){
            if(list[j]<list[j-1]){
                int tmp=list[j];
                list[j]=list[j-1];
                list[j-1]=tmp;
            }
        }
    }
}

最坏时间复杂度：O(n2)

三. 选择排序

基本思想：在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；
第二次遍历n-2个数，找到最小的数值与第二个元素交换；
。。。
第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。
伪代码：

public void selectionSort(int[]list){
    for(int i=0;i<list.lenght;i++){
        int minIndex=i;
        for(j=i+1;j<list.lenght;j++){
            if(a[j]<a[minIndex]){
                minIndex=j;
            }
        }
        if(minIndex!=i){
            int tmp=a[i];
            a[i]=a[minIndex];
            a[minIndex]=tmp;
        }
    }
}

最坏时间复杂度：O(n2)

四. 快速排序

基本思想：分治
实现思路：
1.取key
2.将大于key的放右边，小于key的放左边
3.分别处理左右两边的部分，重复第2步骤
伪代码：

public void quitSort(int[]list,int left,int right){
    int pivot=list[left];
    int pl=lef;int pr=right;
    while(pl<pr){
        while(pl<pr&&list[pr]>pivot){
            pr--;
        }
        list[pl]=list[pr];
        while(pl<pr&& list[pl]<pivot){
               pl++;
        }
        list[pr]=list[pl];
    }
    list[left]=pivot;
    quitSort(list,0,left);
    quitSort(list,left+1,right);
}

最坏时间复杂度：O(n*logn)

五. 归并排序

基本思想：分治
实现思路：
1.将序列不断地拆成两个序列
2.不断地合并两个序列
2.1 设置左边序列的游标，设置右边序列的游标，设置临时数组的开始下标值
2.2 比较左边游标指定的元素值和右边游标指定的元素值，如果小的，把元素值给临时数组，当前游标下移，临时数组游标下移。
2.3 循环2.2步骤直到左游标超过中间值，或者右游标超过数组界限
2.4 将左边或右边剩余序列拷贝到临时数组
2.5 将临时数组的元素复原到原数组
伪代码：

public void mergeSort(int[] data,int left,int right){
    if(left<right){
        int mid=(left+right)/2;
        mergeSort(data,left,mid);//排序左边数组
        mergeSort(data,mid+1,right);//排序右边数组
        merge(data,left,mid,right);//合并两边数组
    }
}
public void merge(int[] data,int left,int mid,int right){
    //初始化两边数组游标
    int pl=left;int pr=mid+1;
    //初始化临时数组
    int[] tmp=new int[data.lenght];
    int k=left;
    //合并两边数组到临时数组
    while(pl<=mid&&pr<=right){
        if(a[pl]<=a[p2]){
            tmp[k++]=a[pl++];
        }else{
            tmp[k++]=a[pr++]
        }
    }
    while(pl<=mid){tmp[k++]=a[pl++];}
    while(pr<=right){tmp[k++]=a[pr++];}
    //将临时数组元素复原到原数组
    for(i=left;i<=right;i++){
        a[i]=tmp[i];
    }
}