排序算法总结

排序算法

参考1

参考2

冒泡排序

排序思想
每次比较交换相邻的元素，每轮遍历将最大值放到最后一个
算法分析
- 平均时间复杂度: O(n^2)
- 最坏时间复杂度: O(n^2)
- 最好时间复杂度: O(n)
- 空间复杂度: O(1)
- 稳定性: 稳定
代码实现

for(int i=1; i<arr.length; i++){
    //比较交换相邻元素
    for(int j=0; j<arr.length-i; j++){
        if(arr[j]>arr[j+1]){
            int temp=arr[j];
            arr[j]=arr[j+1];
            arr[j+1]=temp;
        }
    }
}

选择排序

排序思想
每次选择最小值。先假定第1个数是最小值，再从剩余的数中寻找最小值，若假定的数是最小值则继续往下遍历，否则就交换最小值
算法分析
- 平均时间复杂度: O(n^2)
- 最坏时间复杂度: O(n^2)
- 最好时间复杂度: O(n^2)
- 空间复杂度: O(1)
- 稳定性: 不稳定
代码实现

for(int i=0; i<arr.length; i++){
    int min=arr[i];
    int minIndex=i;
    for(int j=i+1; j<arr.length; j++){
        //若假定的最小值非最小值则交换
        if(min>arr[j]){
            min=arr[j];
            minIndex=j;
        }
    }

    if(min!=arr[i]){
        arr[minIndex]=arr[i];
        arr[i]=min;
    }
}

插入排序

排序思想
将数据分为有序和无序，第1个数有序，从第2个数开始插入到有序中去
算法分析
- 平均时间复杂度: O(n^2)
- 最坏时间复杂度: O(n^2)
- 最好时间复杂度: O(n)
- 空间复杂度: O(1)
- 稳定性: 稳定
代码实现

for(int i=1; i<arr.length; i++){
    int insertValue=arr[i]; //要插入的数
    int insertIndex=i-1;    //要插入的位置
    //排序
    while(insertIndex>=0 && insertValue<arr[insertIndex]){
        //原来的数往后移
        arr[insertIndex+1]=arr[insertIndex];
        insertIndex--;
    }
    arr[insertIndex+1]=insertValue;
}

希尔排序

排序思想
对直接插入排序的优化，每次按length/2分组
算法分析
- 平均时间复杂度: O(nlogn)
- 最坏时间复杂度: O(nlogn)
- 最好时间复杂度: O(nlogn)
- 空间复杂度: O(1)
- 稳定性: 不稳定
代码实现

for(int k=arr.length/2; k>0; k=k/2){
    for(int i=k; i<arr.length; i++){
        for(int j=i-k; j>=0; j=j-k){
            if(arr[j]>arr[j+k]){
                int temp=arr[j];
                arr[j]=arr[j+k];
                arr[j+k]=temp;
            }
        }
    }    
}

归并排序

排序思想

归并排序本质就是不断合并两个有序数组的过程
代码实现

public void mergetsort(int[] arr,int l,int r){
    int m = (l+r)/2;
    if(l<r){
        //递归的归并排序左右数组
        mergetsort(arr,l,m);
        mergetsort(arr,m+1,r);
        //合并左右数组
        mergetsort(arr,l,m,r);
    }
}

private void mergetsort(int[] arr, int l, int m, int r) {
    int[] temp = new int[arr.length];  //辅助数组
    int i=l;   //左边数组指针
    int j=m+1;  //右边数组指针
    int k=0;   //辅助数组指针

    while(i<=m && j<=r){
        if(arr[i]<arr[j]){
            temp[k]=arr[i];
            k++;
            i++;
        }else {
            temp[k]=arr[j];
            k++;
            j++;
        }
    }

    while(i<=m){
        temp[k]=arr[i];
        k++;
        i++;
    }

    while(j<=r){
        temp[k]=arr[j];
        k++;
        j++;
    }

    int s=0;
    for (int n = l; n <= r; n++) {
        arr[n] = temp[s++];
    }
}

快速排序

排序思想

选取关键值，先根据二叉排序树思想，将比关键值小的放左边，比关键值大的放右边[交换两边都不符条件的]，以关键值为中心，左右递归排序。
代码实现

public void quicksort(int arr[],int l,int r){
    int key = arr[(l+r)/2];  //选择中间数作为关键值
    int i=l;
    int j=r;

    if(l>=r){
        return;
    }
    while(i<j){
        //从左边查找小于key的
        while(i<j && arr[i]<key){
            i++;
        }
        //从右边查找大于key的
        while(i<j && arr[j]>key){
            j--;
        }
        //如果左边大于key或者右边小于key就交换
        if(i<j){
            int temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
        }
        //如果左边等于key,j--
        //或者右边等于key,i++
        if(arr[i]==key){
            j--;
        }else if(arr[j]==key){
            i++;
        }
    }

    //循环结束，arr[i]=arr[j]=key
    //左右继续递归
    quicksort(arr,l,i-1);
    quicksort(arr,i+1,r);
}