Java教程

Java排序算法

本文主要是介绍Java排序算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

Java排序算法

  • 1.冒泡排序
    • 1.1冒牌排序的思想
    • 1.2算法描述
    • 1.3代码实现
    • 1.4算法分析
  • 2.选择排序
    • 2.1选择排序的思想
    • 2.2算法描述
    • 2.3代码实现
    • 2.4算法分析
  • 3.插入排序
    • 3.1 插入排序思想
    • 3.2算法描述
    • 3.3代码实现
    • 3.4算法分析
  • 4.堆排序
    • 4.1堆排序的思想
    • 4.2算法描述
    • 4.3代码实现
    • 4.4算法分析
  • 5.希尔排序
    • 5.1希尔排序的思想
    • 5.2算法描述
    • 5.3代码实现
    • 5.4算法分析
  • 6.归并排序
    • 6.1归并排序的思想
    • 6.2算法描述
    • 6.3代码实现
    • 6.4算法分析
  • 7.快速排序
    • 7.1快速排序的思想
    • 7.2算法描述
    • 7.3代码实现
    • 7.4算法分析

1.冒泡排序

1.1冒牌排序的思想

冒泡排序是一种简单的排序算法。它重复的访问要排序的数列,一次进行两个元素的比较操作,如果他们的顺序与预期想法不同则进行元素之间的交换过程。重复进行元素之间的比较操作直到元素不再需要交换,继而该排序过程已经完成。

1.2算法描述

  • 比较相邻元素,如果前者元素大于后者就交换元素。
  • 每次比较都比较的是每一对相邻的元素,一轮过后,最大的元素会出现在最后。
  • 重复上述步骤,直至排序完成。

1.3代码实现

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

上述代码存在重复比较的情况,尤其是若后序排列均为正常排列时,还是会重复比较,所以为了减少这一情况对上述代码进行优化。

public static void optimizedBubbleSort(int[] array){
        if(array==null||array.length==0){
            return;
        }
        //设置标记,如果后续排列均为正常正常排列,则无需继续进行冒泡
        boolean nextSort=true;
        for(int i=0;i<array.length-1&&nextSort;i++){
            nextSort=false;
            for (int j =0;j<array.length-1-i;j++){
                if(array[j]>array[j+1]){
                    int tmp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=tmp;
                    nextSort=true;
                }
            }
        }
    }

1.4算法分析

  • 时间复杂度分析:
    最优时间复杂度:O(n) 最差情况 O(n^2) 平均时间复杂度:O(n^2)
  • 空间复杂度分析: 平均空间复杂度:O(1)
  • 稳定性: 稳定

2.选择排序

2.1选择排序的思想

选择排序的特点:选择排序是不稳定的排序算法,因为无论对什么数据进行排序都是 O(n^2)的时间复杂度,因为选择排序的时间复杂度比较大,所以当使用选择排序的时候,数据规模越小越好。

2.2算法描述

  • 在待排序序列中找到最小(或最大)元素,存放排序序列在起始位置。
  • 在剩余待排序序列中继续寻找最小(或最大)元素排在排序序列的末端。
  • 重复第二步骤,直至序列排序完成。

2.3代码实现

    public static void selectSort(int []array){
        if(array==null||array.length==0){
            return;
        }
        for(int i=0;i<array.length;i++){
            int minIndex=i;
            for(int j=i+1;j<array.length;j++){
                if(array[j]<array[minIndex]){
                    minIndex=j;
                }
            }
            //minIndex是元素最小的下标
            if(minIndex!=i){
                int tmp=array[i];
                array[i]=array[minIndex];
                array[minIndex]=tmp;
            }
        }
    }

优化:在每一次寻找元素的过程中,直接寻找两个元素,即待排序序列中的最大元素和最小元素。

    public static void optimizedSelectSort(int[]array){
        if(array==null||array.length==0){
            return;
        }
        for(int i=0;i<array.length/2;i++){
            int minIndex=i;
            int maxIndex=i;
            for(int j=i+1;j<array.length-1-i;j++){
                if(array[j]<array[minIndex]){
                    minIndex=j;
                    continue;
                }
                if(array[j]>array[maxIndex]){
                    maxIndex=j;
                }
            }

            int tmp=array[i];
            array[i]=array[minIndex];
            array[minIndex]=tmp;
            //判断maxIndex的值是否就是i
            if(maxIndex==i){
                maxIndex=minIndex;
            }
            tmp=array[maxIndex];
            array[maxIndex]=array[array.length-1-i];
            array[array.length-1-i]=tmp;
        }
    }

2.4算法分析

  • 时间复杂度分析:
    最优时间复杂度 O(n^2) 平均时间复杂度 O(n^2) 最坏时间复杂度 O(n^2)
  • 空间复杂度分析: 平均空间复杂度:O(1)
  • 稳定性: 不稳定

3.插入排序

3.1 插入排序思想

插入排序的算法是通过构建有序序列,对于未排序的数据,在已排序的序列中从后向前进行查找操作,找到满足条件的元 素之后进行位置插入操作。

3.2算法描述

  • 从第一个元素开始,该元素可以认为已经是排序好的元素;
  • 取出下一个元素,在已经排序好了的元素中从后向前进行查找;
  • 如果已经排序好的元素大于新元素,将该元素移动到下一个位置;
  • 重复步骤3,直到找到找到已排序好的元素小于或等于新元素,进行元素的插入动作。

3.3代码实现

    public static void insertSort(int []array){
        if(array==null||array.length==0){
            return;
        }
        for(int i=0;i<array.length;i++){
            int tmp=array[i];//拿到的元素
            int j=i;
            while(j>0&&tmp<array[j-1]){
                array[j]=array[j-1];
                j--;
            }
            array[j]=tmp;
        }
    }

3.4算法分析

  • 时间复杂度分析:
  • 最优时间复杂度:O(n) 平均时间复杂度:O(n^2) 最差时间复杂度:O(n^2)
  • -空间复杂度分析: 平均空间复杂度:O(1)
  • 稳定性分析: 稳定

4.堆排序

4.1堆排序的思想

堆是一棵顺序存储的完全二叉树。完全二叉树中所有非终端节点的值均不大于(或不小于)其左、右孩子节点的值。其中 每个节点的值小于等于其左、右孩子的值,这样的堆称为小根堆;其中每个节点的值大于等于其左、右孩子的值,这样的堆称 为大根堆
堆排序是指利用堆这种数据结构进行设计的一种排序算法。堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小) 这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
在这里插入图片描述

4.2算法描述

用大根堆排序的基本思想:

  • 先将初始数组建成一个大根堆,此堆为初始的无序
  • 再将关键字最大的记录 R[ 1 ] (即堆顶)和无序区的最后一个记录 R[n]交换,由此得到新的无序区 R[1…n-1]和有 序区 R[n]。由于交换后新的根 R[1]可能违反堆性质,故应将当前无序区 R[1…n-1]调整为堆。然后再次将 R[1…n-1]中关键字最大的记录 R[1]和该区间的最后一个记录 R[n-1]交换,由此得到新的无序区 R[1…n-2]和有 序区 R[n-1…n],同样要将 R[1…n-2]调整为堆。
  • …… 直到无序区只有一个元素为止。
    堆排序堆排序首先是根据元素构建堆。然后将堆的根节点取出(一般是与最后一个节点进行交换),将前面 len-1 个节点 继续进行堆调整的过程,然后再将根节点取出,这样一直到所有节点都取出。

4.3代码实现

    private static <T>void swap(T[] arr,int index1,int index2){ 
        T temp = arr[index1]; 
        arr[index1] = arr[index2]; 
        arr[index2] = temp; 
    } 
    private static <T extends Comparable<T>>void adjust(T[] arr,int start,int end){ 
        T temp=arr[start]; 
        for(int i=2*start+1;i<=end;i=2*i+1){ 
            if(i+1<=end && arr[i].compareTo(arr[i+1]) < 0){ 
                i++;//i 保存左右孩子较大值的下标 
                 } 
            if(temp.compareTo(arr[i]) < 0){ 
                arr[start]=arr[i]; 
                start=i; 
            }
            else{ 
                break; 
            } 
        } 
        arr[start]=temp; 
    } 
    public static <T extends Comparable<T>>void heapSort(T[] arr){ 
        int i=0; 
        for(i=(arr.length-1-1)/2;i>=0;i--){//i 代表要调整根节点的下标 
             adjust(arr, i, arr.length-1);//最大堆建立好了 
             } 
        for(i=0;i<arr.length;i++){ 
            //0 下标 根保存最大值  
            // arr[0]和堆中相对的"最后"元素进行交换 
             swap(arr,0,arr.length-1-i); 
             adjust(arr, 0, arr.length-1-i-1); 
        } 
    }

4.4算法分析

  • 时间复杂度分析:
  • 最优时间复杂度:O(nlog2n) 平均时间复杂度:O(nlog2n) 最坏时间复杂度:O(nlog2n)
  • 空间复杂度分析: O(1)
  • 稳定性分析: 不稳定

5.希尔排序

5.1希尔排序的思想

希尔排序也是一种插入排序,它是简单插入排序的一种算法改进方式。也成为见效增量排序,希尔排序的时间复杂度相比 直接插入排序的时间复杂度要小。他与直接插入排序的不同在于它会优先比较距离较远的元素。希尔排序是按照一定的增量进 行分组排序,对每一组进行直接插入排序,随着分组个数的减少,每组中的元素就会越来越多,当增量减少为 1 时,排序结束。

5.2算法描述

选择增量 gap=length/2;缩小增量继续以 gap=gap/2 的方式进行分组。{n/2,(n/2)/2,(n/2)/4,…,1}增量序列。

  • 选择一个增量序列,按照增量序列个数 m,进行 m 趟排序。
  • 每趟排序根据对应的增量次数分别进行元素的分组操作,对组内进行直接插入排序操作。
  • 继续下一个增量,分别进行分组直接插入操作。
  • 重复第三个步骤,直到增量变成 1,所有元素在一个分组内,希尔排序结束。

5.3代码实现

     public static <T extends Comparable<T>>void shellSort(T[] arr,int gap){
        int i=0,j=0; 
        for(i=gap;i<arr.length;i++){ 
            T temp = arr[i];
            for(j=i-gap;j>=0;j-=gap){ 
                if(temp.compareTo(arr[j]) < 0){ 
                    arr[j+gap]=arr[j]; 
                } 
                else{ 
                    break; 
                } 
            } 
            arr[j+gap]=temp; 
        } 
    } 
    public static <T extends Comparable<T>>void shell(T[] arr){ 
        int[] partition={5,3,1};
        for(int i=0;i<partition.length;i++){ 
            shellSort(arr,partition[i]); 
        } 
    }

5.4算法分析

  • 时间复杂度分析: 平均时间复杂度:O(n1.3~n1.5)
  • 空间复杂度分析: O(1)
  • 稳定性分析: 不稳定

6.归并排序

6.1归并排序的思想

归并排序建立在归并的有效操作上进行排序,主要采用分治法将已有序的子序列合并,得到完全有序的序列。即先让每一 小段有序,再让小段之间变得有序。若将两个有序合成一个有序段,这又称为二路归并。

6.2算法描述

  • 开始以间隔为 1 的进行归并,也就是说,第一个元素跟第二个进行归并。第三个与第四个进行归并;
  • 然后,再以间隔为 2 的进行归并,1-4 进行归并,5-8 进行归并;
  • 再以 2 * 2 的间隔,同理,直到 2*k 超过数组长度为止。
  • 当不够两组进行归并时,如果超过 k 个元素,仍然进行归并;如果剩余元素不超过 k 个元素,那么直接复制给中间数组。

6.3代码实现

public static <T extends Comparable<T>>void merge(T[] arr,int len,int gap){ 
        int low1=0;//第一个归并段的起始下标 
        int high1=low1+gap-1;//第一个归并段的结束下标
        int low2=high1+1;//第二个归并段起始下标 
        int high2=low2+gap-1 > len-1?len-1:low2+gap-1; 
        T[] brr=(T[])new Comparable[arr.length]; 
        int i=0; 
        while(low2 < len){//保证有两个归并段 
             while(low1<=high1 && low2<=high2){//两个归并段都有数据时继续判断 
                  if(arr[low1].compareTo(arr[low2]) <= 0){ 
                      brr[i++]=arr[low1++]; 
                  } 
                  else{ 
                      brr[i++]=arr[low2++]; 
                  } 
             } 
             while(low1<=high1){//第一个归并段还有数据 
                 brr[i++]=arr[low1++]; 
             } 
             while(low2<=high2){ 
                 brr[i++]=arr[low2++]; 
             } 
             low1=high2+1; 
             high1=low1+gap-1; 
             low2=high1+1; 
             high2 = low2+gap-1 > len-1?len-1:low2+gap-1; 
        } 
        //没有两个归并段:单的直接拷贝下来 
         while(low1<=len-1){ 
             brr[i++]=arr[low1++]; 
         } 
         for(i=0;i<arr.length;i++){ 
             arr[i]=brr[i];
         }
         brr=null; 
    } 
    public static <T extends Comparable<T>>void mergeSort(T[] arr){ 
        for(int i=1;i<arr.length;i*=2){//2 个 2 个有序,4 个 4 个有序... 
             merge(arr,arr.length,i); 
        } 
    }

在这里插入图片描述

6.4算法分析

  • 时间复杂度分析: 平均时间复杂度:O(nlog2n) 最坏时间复杂度:O(nlog2n)
  • 空间复杂度分析: O(n)
  • 稳定性分析: 稳定

7.快速排序

7.1快速排序的思想

快排主要是通过选择一个关键值作为基准值。比基准值小的都在左边序列(一般是无序的),比基准值大的都在右边(一 般是无序的)。依此递归,达到总体待排序序列都有序。

7.2算法描述

  • 选择基准:在待排序列中,按照某种方式挑出一个元素,作为 “基准”(pivot)
  • 分割操作:以该基准在序列中的实际位置,把序列分成两个子序列。此时,在基准左边的元素都比该基准小,在基准右边 的元素都比基准大
  • 递归地对两个序列进行快速排序,直到序列为空或者只有一个元素。

7.3代码实现

三位数取中

 //随机
    //中位数三位取中
    public static int RandParition(int []arr,int left,int right){
        Random random=new Random();
        int index=random.nextInt((right-left)+1)+left;
        int tmp=arr[left];
        arr[left]=arr[index];
        arr[index]=tmp;
        return Parition(arr,left,right);
    }
    public static void QuickSort(int []arr){
        QuickPass(arr,0,arr.length-1);
    }
    public static int Parition(int []arr,int left,int right){
        int i=left,j=right;
        int tmp=arr[i];
        while (i<j){
            while (i<j&&arr[j]>tmp)--j;
            if(i<j)arr[i]=arr[j];
            while (i<j&&arr[i]<=tmp)++i;
            if(i<j)arr[j]=arr[i];
        }
        arr[i]=tmp;
        return i;
    }

非递归

     public static void QuickPass(int []arr,int left,int right) {
         Queue<Integer> queue = new LinkedList<>();
         if (left >= right) return;
         queue.offer(left);
         queue.offer(right);
         while (!queue.isEmpty()) {
             left = queue.poll();
             right = queue.poll();
             int pos = OWParition2(arr, left, right);
             if (left < pos - 1) {
                 queue.offer(left);
                 queue.offer((pos - 1));
             }
             if (pos + 1 < right) {
                 queue.offer(pos + 1);
                 queue.offer(right);
             }
         }
     }
     public static int OWParition2(int []arr,int left,int right){
        int i=left,j=left+1;
        int tmp=arr[i];
        while (j<=right){
            if(arr[j]<=tmp){
                i+=1;
               Swap(arr,i,j);
            }
                j++;
        }
        Swap(arr,left,i);
        return  i;
    }
    public static void Swap(int[]arr,int i,int j){
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }

递归

public static void QuickSort(int []arr){
        QuickPass(arr,0,arr.length-1);
    }
    //    利用递归
    public static void QuickPass(int []arr,int left,int right){
        if(left<right){
            int pos=Parition(arr,left,right);
            QuickPass(arr,left,pos-1);
            QuickPass(arr,pos+1,right);
        }
    }
     public static int Parition(int []arr,int left,int right){
        int i=left,j=right;
        int tmp=arr[i];
        while (i<j){
            while (i<j&&arr[j]>tmp)--j;
            if(i<j)arr[i]=arr[j];
            while (i<j&&arr[i]<=tmp)++i;
            if(i<j)arr[j]=arr[i];
        }
        arr[i]=tmp;
        return i;
    }

7.4算法分析

  • 时间复杂度分析:
    最优时间复杂度:O(nlog2n) 平均时间复杂度:O(nlog2n) 最坏时间复杂度:O(nlog2n)
  • 空间复杂度分析: Olog2n)
  • 稳定性分析: 不稳定
这篇关于Java排序算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!