最新消息:深度思考

经典排序算法汇总

算法 liuxuecheng 2324浏览 0评论

1.冒泡排序

是一种稳定的排序方式,时间复杂度O(n^2)。列出三种逐次优化的实现方法:
1.1 最普通

public class BubbleSortV1 {
    public static void bubbleSort(int[] array){
        for(int i=0;i<array.length;i++){
            for(int j = i+1;j<array.length;j++){
                if(array[i]>array[j]){
                    int tmp = array[i];
                    array[i] = array[j];
                    array[j] = tmp;
                }
            }
        }
    }

1.2 改进一点,从后往前循环,比较的过程中顺便交换元素位置。

public class BubbleSortV2 {
    public static void bubbleSort(int[] array){
        for(int i = 0;i<array.length;i++){
            for(int j = array.length-1;j>i;j--){
                if(array[j]<array[j-1]){
                    int tmp = array[j];
                    array[j] = array[j-1];
                    array[j-1] = tmp;
                }
            }
        }
    }
}

1.3 增加标志位,减少无效循环。

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

2.简单选择排序

冒泡排序的一种,优点在于省略了冒泡排序中频繁的交换操作。是一种稳定的排序方式,时间复杂度O(n^2)

public class SelectSort {
    public static void selectSort(int[] array){
        for(int i=0;i<array.length;i++){
            int m = i;
            for(int j=i+1;j<array.length;j++){
                if(array[j]<array[m]){
                    m = j;
                }
            }
            if(i!=m){
                int tmp = array[i];
                array[i] = array[m];
                array[m] = tmp;
            }
        }
    }
}

3.直接插入排序

是一种不稳定的排序方式,时间复杂度为O(n^2),但是性能比冒泡和简单选择排序要好。

public class InsertSort {
    public static void insertSort(int[] array){
        for(int i=1;i<array.length;i++){
                for(int j = i;j>0;j--){
                    if(array[j]<array[j-1]){
                        int tmp = array[j];
                        array[j] = array[j-1];
                        array[j-1] = tmp;
                    }else{
                        break;
                    }
                }
        }
    }
}

4.希尔排序

希尔排序的基本思路是将待排序列划分成间距为gap的多个子序列,子序列内通过插入排序的方式进行排序,使整个序列趋向于有序,然后不断的缩减gap到1。
希尔排序是一种不稳定的排序方式,时间复杂度为O(NlogN)

public class ShellSort {
    public static void shellSort(int[] array){
        int length = array.length;
        int j;
        for(int gap = length/2;gap>0;gap = gap/2){
            for(int i = gap;i<length;i++){
                int tmp = array[i];
                for(j = i; j>=gap&&tmp<array[j-gap]; j=j-gap){
                   array[j] = array[j-gap];
                }
                array[j] = tmp;
            }
        }
    }
}

5.堆排序

升序排序使用大顶堆的性质,不断的从堆顶获取值放到序列的最后一位。
堆排序是一种不稳定的排序方式,其最好、最坏、平均时间复杂度均为O(NlogN)

public class HeapSort {

    public static void heapSort(int[] array){
        for(int i = array.length/2-1;i>=0;i--){
            adjustHeap(array,i,array.length);
        }

        for(int j = array.length-1;j>0;j--){
            swap(array,0,j);
            adjustHeap(array,0,j);
        }
    }

    public static void adjustHeap(int[] array,int start,int end){
        int tmp = array[start];
        for(int k = start*2+1;k<end;k=k*2+1){
            if(k+1<end&&array[k]<array[k+1]){
                ++k;
            }
            if(tmp<array[k]){
                array[start] = array[k];
                start = k;
            }else {
                break;
            }
        }
        array[start] = tmp;
    }

    public static void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i]= array[j];
        array[j] = tmp;
    }
}

6.归并排序

是一种稳定的排序算法,时间复杂度O(NlogN)

public class MergeSort {

    public static void mergeSort(int[] array,int left,int right,int[] tmp){
        if(left<right){
            int mid = (left+right)/2;
            mergeSort(array,left,mid,tmp);
            mergeSort(array,mid+1,right,tmp);
            merge(array,left,mid,right,tmp);
        }
    }

    private static void merge(int[] array,int left,int mid,int right,int[] tmp){
        int i = left;
        int j = mid+1;
        int t = 0;
        while(i<=mid && j<=right){
            if(array[i]<=array[j]){
                tmp[t++] = array[i++];
            }else{
                tmp[t++] = array[j++];
            }
        }

        while (i<=mid){
            tmp[t++] = array[i++];
        }

        while (j<=right){
            tmp[t++] = array[j++];
        }

        t = 0;
        while (left <= right){
            array[left++] = tmp[t++];
        }
    }
}

7.快速排序

快速排序是一种不稳定的排序方法,时间复杂度为O(NlogN)

public class QuickSort {

    public static void quickSort(int[] array,int low,int high){
        int pivot;
        if(low<high){
            pivot = partition(array,low,high);
            quickSort(array,low,pivot-1);
            quickSort(array,pivot+1,high);
        }
    }

    private static int partition(int[] array,int low,int high){
        int pivotValue = array[low];
        while (low<high){
            while(low<high&&array[high]>=pivotValue){
                high--;
            }
            swap(array,low,high);
            while(low<high&&array[low]<=pivotValue){
                low++;
            }
            swap(array,low,high);
        }

        return low;
    }

    private static void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i]= array[j];
        array[j] = tmp;
    }
}

转载请注明:大数据随笔 » 经典排序算法汇总

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址