1. 首页
  2. 文章资讯

Java:数据结构-排序

24 阅读 0 评论

排序

排序的概念：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。 

常见排序算法的实现

1.直接插入排序

性质：

  1. 元素集合越接近有序，直接插入排序算法的时间效率越高
  2. 时间复杂度：O(N^2)
  3. 空间复杂度：O(1)，它是一种稳定的排序算法
  4. 稳定性：稳定

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

2. 希尔排序

性质：

稳定性：不稳定的
时间复杂度：n^1.3  - n^1.5
空间复杂度：O(1)

public void shallSort(int[] array,int gap){
        gap=array.length;
        while (gap>1){
            gap/=2;
            shall(array,gap);
        }
    }
    public static void shall(int[] array,int gap){
        for (int i = gap; i <array.length; i++) {
            int tem=array[i];
            int j = i-gap;
            for (; j>0 ; j-=gap) {
                if(array[j]>tem){
                    array[j+gap]=array[j];
                }else {
                    array[j+gap]=tem;
                    break;
                }
            }
            array[j+gap]=tem;
        }
    }

3. 选择排序

性质：

   时间复杂度：O(N^2)

       和数据 是否有序无关

   空间复杂度：O(1)

   稳定性：不稳定的排序

 public void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int num=i;
            int j =i-1;
            for (; j <array.length ; j++) {
                if(array[j]<array[num]){
                    num=j;
                }
            }
            swap(array,i,j);
        }
    }
    public static void swap(int[] array, int i, int j){
        int tem=array[i];
        array[i]=array[j];
        array[j]=tem;
    }

优化为（同时找最大值和最小值）

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

    public void selectSort1(int[] array){
        int left=0;
        int right=array.length;
        while (left<right) {
            int min=left;
            int max=left;
            for (int i = left + 1; i <=right; i++) {
                if(array[i]>array[max]){
                    max=i;
                }
                if(array[i]<min){
                    min=i;
                }
            }

            swap(array,left,min);
            if (left==max){
                max=min;
            }
            swap(array,right,max);
            left++;
            right--;
        }
    }

4.堆排序

时间复杂度：O(n*logN)

空间复杂度：O(1)

稳定性：不稳定

heapSort(int[] array)方法的作用：主方法，执行堆排序的整体流程

createHeap(int[] array)方法的作用：将输入数组构建成一个最大堆

siftDown(int[] array, int parent, int length)方法的作用：在堆中调整节点，以维持最大堆的性质。

public static void heapSort(int[] array){
        createHeap(array);
        int end=array.length-1;
        while (end>0){
            swap(array,0,end);
            siftDown(array,0,end);
            end--;
        }
    }

    public static void createHeap(int[] array){
        for (int parent=(array.length-1-1)/2;parent>=0;parent--){
            siftDown(array,parent, array.length);
        }
    }
    public static void siftDown(int[] array,int parent,int length){
        int child=parent*2+1;
        while (child<length){
            if (child+1<length && array[child]<array[child+1]){
                child++;
            }
            if (array[child]>array[parent]){
                swap(array,child,parent);
                parent=child;
                child=2*parent+1;
            }else {
                break;
            }
        }
    }

5.冒泡排序

时间复杂度：讨论 没有优化的情况下，也就是 没有下方的boolean元素和-i操作168 * O(N^2)

空间复杂度：O(1)

稳定性：稳定的排序

如果有1000个数，得判断999次，但是有可能5次就排好序了，为了防止排好序还继续判断，所以我们优化了一下代码，如果不进入循环，那么我们判断已经排好序了，可以直接break。

public static void bubbleSort(int[] array){
        boolean flg=false;
        for (int i=0;i<array.length;i++){
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flg=true;
                }
            }
            if(!flg){
                break;
            }
        }
    }

6.快速排序

时间复杂度：  

最坏情况：当数据给定的是1 2 3 4 5 6 7.....有序的情况下 确实是O(n^2)  9 8 7 6 5 4  

最好情况：O(N*logN)  

空间复杂度：  

最坏情况：O(N)  

最好情况：O(logN)  

稳定性：不稳定性

1.Hoare版

public void quickSort(int[] array){
        quick(array,0,array.length-1);
    }
    private void quick(int[] array,int start,int end){
        if(start>end){
            return;
        }
        int mid=partition(array,start,end);
        quick(array,start,mid-1);
        quick(array,mid+1,end);
    }

    private int partition(int[] array, int left, int right) {
        int key=array[left];
        int ketPotion=left;
        while (left<right){
            while (left<right && array[right]>=key){
                right--;
            }
            while (left<right && array[left]<=key){
                left++;
            }
            swap(array,left,right);
        }
        swap(array,ketPotion,left);
        return left;
    }

注：

1.为什么从后往前找，而不是从前往后找呢？

如果从前往后，则会出现这种情况

2.为什么这里会有等号

 

如果没有等号，就会出现死循环的情况。

2.挖坑法

private int partition1(int[] array, int left, int right) {
        int key=array[left];
        while (left<right){
            while (left<right && array[right]>=key){
                right--;
            }
            array[left]=array[right];
            while (left<right && array[left]<=key){
                left++;
            }
            array[right]=array[left];
        }
        array[left]=key;
        return left;
    }

3.前后指针法

private int partition2(int[] array,int left,int right){
        int cur=left+1;
        int prev=left;
        while (cur<=right){
            if(array[cur]<array[left] && array[prev++]!=array[cur]){
                swap(array,prev,cur);
            }
            cur++;
        }
        swap(array,left,prev);
        return prev;
    }

 快速排序的优化：

1.三数取中法（找mid）

因为一组数据如果正好是顺序的，会使快排的时间复杂度为O(n2)，三数取中法选取的枢轴更接近数组的中位数，从而更有可能将数组划分为两部分，使得递归树更加平衡，提高整体效率，通过三数取中法，快速排序的平均时间复杂度更接近 O(nlog⁡n)。

private void quick(int[] array,int start,int end){
        if(start>end){
            return;
        }
        int midIndex=getMidNumber(array,start,end);
        swap(array,start,midIndex);
        int mid=partition(array,start,end);
        quick(array,start,mid-1);
        quick(array,mid+1,end);
    }
    
    private int getMidNumber(int[] array,int start,int end){
        int mid=(start+end)/2;
        if(array[start]>array[end]){
            if(array[end]>array[mid]){
                return end;
            }else if (array[mid]>array[start]){
                return start;
            }else {
                return mid;
            }
        }else {
            if(array[start]>array[mid]){
                return start;
            }else if(array[mid]>array[end]){
                return end;
            }else {
                return mid;
            }
        }
    }

2.在接近有序时，使用快速排序（在一定的小区间）

public void quickSort(int[] array){
        quick(array,0,array.length-1);
    }
    private void quick(int[] array,int start,int end){
        if(start>end){
            return;
        }
        if(end-start+1<=10){
            insetSortRange(array,start,end);
            return;
        }
        int midIndex=getMidNumber(array,start,end);
        swap(array,start,midIndex);
        int mid=partition(array,start,end);
        quick(array,start,mid-1);
        quick(array,mid+1,end);
    }

    private int getMidNumber(int[] array,int start,int end){
        int mid=(start+end)/2;
        if(array[start]>array[end]){
            if(array[end]>array[mid]){
                return end;
            }else if (array[mid]>array[start]){
                return start;
            }else {
                return mid;
            }
        }else {
            if(array[start]>array[mid]){
                return start;
            }else if(array[mid]>array[end]){
                return end;
            }else {
                return mid;
            }
        }
    }
    public static void insetSortRange(int[] array,int start,int end){
        for (int i = start+1; i <end; i++) {
            int tem=array[i];
            int j = i-1;
            for (; j>0 ; j--) {
                if(array[j]>tem){
                    array[j+1]=array[j];
                }else {
                    array[j+1]=tem;
                    break;
                }
            }
            array[j+1]=tem;
        }
    }

快排的非递归形式：

利用栈来做，通过使用栈来模拟递归过程，处理当前范围的数组，并将分区后的左右子数组的范围压入栈中，直到所有范围都处理完毕，每次调用 partition 方法都会把数组根据基准值分成两部分，确保左侧部分的所有元素都小于基准值，右侧部分的所有元素都大于基准值。这样，基准值最终会处于其正确的位置上。

public void quickSortNor(int[] array,int start,int end){
        if(array.length<=0){
            return;
        }
        int pilot=partition(array,start,end);
        Stack<Integer> stack=new Stack<>();
        if(start+1<pilot){
            stack.push(start);
            stack.push(pilot-1);
        }
        if (end-1>pilot){
            stack.push(pilot+1);
            stack.push(end);
        }
        while (stack.isEmpty()){
            start=stack.pop();
            end=stack.pop();
            pilot=partition(array,start,end);
            if(start+1<pilot){
                stack.push(start);
                stack.push(pilot-1);
            }
            if (end-1>pilot){
                stack.push(pilot+1);
                stack.push(end);
            }
        }
    }
 private int partition(int[] array, int left, int right) {
        int key=array[left];
        int ketPotion=left;
        while (left<right){
            while (left<right && array[right]>=key){
                right--;
            }
            while (left<right && array[left]<=key){
                left++;
            }
            swap(array,left,right);
        }
        swap(array,ketPotion,left);
        return left;
    }

7.归并排序

拆分：

合并：

public void mergeSort(int[] array){
        message(array,0,array.length-1);
    }
    public void message(int[] array,int left,int right){
        //拆分
        if(left>=right){
            return;
        }
        int mid=(left+right)/2;
        message(array,left,mid);
        message(array,mid+1,right);
        //合并
        merge(array,left,right,mid);
    }

    private void merge(int[] array, int left, int right,int mid) {
        int[] tem=new int[10];
        int k=0;
        int s1=left;
        int s2=mid+1;
        while (s1<=mid && s2<=right){
            if (array[s1]<=array[s2]){
                //tem[k++]=array[s1++];
                tem[k]=array[s1];
                k++;
                s1++;
            }else {
                //tem[k++]=array[s2++];
                tem[k]=array[s2];
                k++;
                s2++;
            }
        }
        while (s1<=mid){
            tem[k++]=array[s1++];
        }
        while (s2<=mid){
            tem[k++]=array[s2++];
        }

        for (int i = 0; i < k; i++) {
            array[i+left]=tem[i];
        }
    }

归并排序的非递归形式：

public void messageNorSort(int[] array){
        int gap=1;
        while (gap<=array.length-1){
            for (int i = 0; i <array.length ; i=i+gap*2) {
                int left=i;
                int mid=left+gap-1;
                if(mid>=array.length){
                    mid=array.length-1;
                }
                int right=mid+gap;
                if(right>=array.length){
                    right=array.length-1;
                }
                merge(array,left,right,mid);
            }
            gap*=2;
        }
    }
private void merge(int[] array, int left, int right,int mid) {
        int[] tem=new int[10];
        int k=0;
        int s1=left;
        int s2=mid+1;
        while (s1<=mid && s2<=right){
            if (array[s1]<=array[s2]){
                //tem[k++]=array[s1++];
                tem[k]=array[s1];
                k++;
                s1++;
            }else {
                //tem[k++]=array[s2++];
                tem[k]=array[s2];
                k++;
                s2++;
            }
        }
        while (s1<=mid){
            tem[k++]=array[s1++];
        }
        while (s2<=mid){
            tem[k++]=array[s2++];
        }

        for (int i = 0; i < k; i++) {
            array[i+left]=tem[i];
        }
    }

8.其他排序

1.计数排序：

public void countSort(int[] array){
        //找出最大值和最小值
        int maxVal=array[0];
        int minVal=array[0];
        for (int i = 0; i < array.length; i++) {
            if(array[i]>maxVal){
                maxVal=array[i];
            }
            if(array[i]<minVal){
                minVal=array[i];
            }
        }
        int len=maxVal=minVal+1;
        int[] count=new int[len];
        for (int i = 0; i < array.length; i++) {
            int index=array[i];
            count[index+minVal]++;
        }
        int index=0;
        for (int i = 0; i < count.length; i++) {
            while (count[i]!=0){
                array[index]=count[i+minVal];
                index++;
                count[i]--;
            }
        }
        
    }

2.基数排序

3.桶排序 

希望能对大家有所帮助！！！！

本站资源均来自互联网，仅供研究学习，禁止违法使用和商用，产生法律纠纷本站概不负责！如果侵犯了您的权益请与我们联系！

转载请注明出处： 免费源码网-免费的源码资源网站 » Java:数据结构-排序

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

 发表
评论 返回
顶部