八种排序算法的Java实现

客官°小女子只卖身不卖艺 2022-12-11 09:17 168阅读 0赞

## 一、冒泡排序 ##

### 定义 ###

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

### 代码 ###

public class BubbleSort {
        
        public static void main(String[] args) {
        
            int[] a=new int[]{
        100,2,6,-1,98,70};
            bubbleSort(a);
            System.out.println(Arrays.toString(a));
        }
    
        public static void bubbleSort(int[] arr){
        
            for(int i=0;i<arr.length-1;i++){
        
                for(int j=0;j< arr.length-1-i;j++){
        
                    if(arr[j]>arr[j+1]){
        
                        int t=arr[j];
                        arr[j]=arr[j+1];
                        arr[j+1]=t;
                    }
                }
            }
        }
    }

[冒泡排序讲解视频][Link 1]

## 二、选择排序 ##

### 定义 ###

第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

### 代码 ###

public class SelectSort {
        
        public static void main(String[] args) {
        
            int[] a=new int[]{
        100,2,6,-1,98,70};
            selectSort(a);
            System.out.println(Arrays.toString(a));
    
        }
        /*
        选择排序
         */
        public static void selectSort(int[] arr){
        
            for(int i=0;i<arr.length-1;i++){
        
                for(int j=i+1;j<= arr.length-1;j++){
        
                    if(arr[i]>arr[j]){
        
                        int t=arr[j];
                        arr[j]=arr[i];
                        arr[i]=t;
                    }
                }
            }
        }
    }

[选择排序讲解视频][Link 2]

## 三、插入排序 ##

### 定义 ###

插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

### 代码 ###

public class InsertSort {
        
        public static void insertSort(int[] arr){
        
            for(int i=1;i<arr.length;i++){
        
                for(int j=0;j<i;j++){
        
                    if(arr[i]<arr[j]){
        
                        int t=arr[j];
                        arr[j]=arr[i];
                        arr[i]=t;
                    }
                }
            }
        }
    }

[插入排序讲解视频][Link 3]

## 四、快速排序 ##

### 定义 ###

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

### 代码 ###

public class QuickSort {
        
        //快速排序
        public static void quickSort(int[]arr,int start,int end){
        
            if(start<end){
        
                int index=getIndex(arr,start,end);
    //            System.out.println(Arrays.toString(arr));
                quickSort(arr,start,index-1);
                quickSort(arr,index+1,end);
            }
        }
    
        private static int getIndex(int[] arr, int start, int end) {
        
            int i=start;
            int j=end;
            int x=arr[i];
            while (i<j){
        
                while(i<j&&arr[j]>x)
                    j--;
                if(i<j){
        
                    arr[i]=arr[j];
                    i++;
                }
                while(i<j&&arr[i]<x){
        
                    i++;
                }
                if(i<j){
        
                    arr[j]=arr[i];
                    j--;
                }
            }
            arr[i]=x;
            return i;
        }
    }

**递归的方法一定要注意跳出的条件，一定要有！！！**  
[快速排序讲解视频][Link 4]

## 五、希尔排序 ##

### 定义 ###

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

### 关键 ###

选择合适的增量

#### 克努特序列 ####

interval=1  
interval=interval\*3+1

int interval=1;
    while(interval<arr.length/3){
        
    	interval=interval*3+1;
    }

得到的间隔就是第一次所用的最大增量

### 代码 ###

public class ShellSort {
        
        //希尔排序
        
        public static void shellSort(int[]arr){
        
            //确定intervald的值
            int interval=1;
            while (interval<arr.length/3)
                interval=interval*3+1;
    //        System.out.println("interval+"+interval);
            
            //每一组是穿插着排序的，把同一数量的排完之后再排更多数量的
            for(;interval>0;interval=(interval-1)/3)
                for(int i=interval;i<arr.length;i++){
        
                    int j=i;
                    while(j-interval>=0&&arr[j]<arr[j-interval]){
        
                        Swap.swap(arr,j,j-interval);
                        j-=interval;
                    }
                }
        }
    }

[希尔排序讲解视频][Link 5]

## 六、归并排序 ##

### 定义 ###

归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

#### 拆分的那一步在调用参数时完成，归并这一步使用方法完成。 ####

### 代码 ###

public class MergeSort {
        
        public static void mergeSort(int[]arr,int start,int end){
        
            if(start<end){
        
                mergeSort(arr,start,(end+start)/2);
                mergeSort(arr,(end+start)/2+1,end);
                merger(arr,start,(end+start)/2,end);
            }
        }
        public static void merger(int[]arr,int start,int center,int end){
        
            int[] temporary=new int[end-start+1];
            int i=start;
            int j=center+1;
            int x=0;
            while (i<=center&&j<=end){
        
                if(arr[i]<arr[j]){
        
                    temporary[x]=arr[i];
                    i++;
                }else {
        
                    temporary[x]=arr[j];
                    j++;
                }
                x++;
            }
            if(i<=center){
        
                for(;i<=center;i++,x++){
        
                    temporary[x]=arr[i];
                }
            }
            if(j<=end){
        
                for(;j<=end;j++,x++){
        
                    temporary[x]=arr[j];
                }
            }
            System.out.println(Arrays.toString(temporary));
            for(i=0;i<=temporary.length-1;i++){
        
                arr[start+i]=temporary[i];
            }
        }
    }

[归并排序讲解视频][Link 6]

### 注意 ###

1.  中间索引是（start+end）/2，是加不是减

## 七、基数排序（桶排序） ##

### 定义 ###

基数排序属于“分配式排序”，又称“桶子法”，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog®m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

### 代码 ###

public class BucketSort {
        
        public static void bucketSort(int[]arr) {
        
            int max=getMax(arr);
            int[][] bucket=new int[10][arr.length];
            int[] count=new int[10];
            int digit=String.valueOf(max).length();
            for(int i=0,n=1;i<digit;i++,n*=10){
        
                for(int t=0;t<count.length;t++){
        
                    count[t]=0;
                }
                for(int j=0;j<arr.length;j++){
        
                    int t=arr[j]/n%10;
                    bucket[t][count[t]]=arr[j];
                    count[t]++;
                }
    
    
                int num=0;
                for(int u=0;u<10;u++){
        
                    for(int v=0;v<arr.length;v++){
        
                        if(bucket[u][v]!=0){
        
                            arr[num]=bucket[u][v];
                            num++;
                        }
                    }
                }
                for(int u=0;u<10;u++){
        
                    for(int v=0;v<arr.length;v++){
        
                        bucket[u][v]=0;
                    }
                }
    
            }
    
        }
        private static int getMax(int[] arr) {
        
            int max=arr[0];
            for(int i=1;i<arr.length;i++){
        
                max=max>arr[i]?max:arr[i];
            }
            return max;
        }
    }

[基数排序讲解视频][Link 7]

## 八、堆排序 ##

### 定义 ###

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

#### 大顶堆：上面一层一定比下面一层大 ####

公式：arr\[i\]>arr\[2*i+1\]&&arr\[i\]>arr\[2*i+2\]

#### 小顶堆：上面一层一定比下面一层小 ####

公式：arr\[i\]<arr\[2*i+1\]&&arr\[i\]<arr\[2*i+2\]

#### 最先开始调整的位置：（arr.length-1)/2 ####

### 过程 ###

1.  转成大顶堆，从最后一个非叶子节点开始转。
2.  for循环\{  
    将数组第一位与最后一位调换；  
    将除最后一位以外的数组转成大顶堆（索引只需要写arr【0】）；  
    \}

### 代码 ###

public class HeapSort {
        
        public static void heapSort(int[]arr){
        
            //转成大顶堆
            int index=(arr.length-1)/2;
            for(int i=index;i>=0;i--){
        
                getMaxHeap(arr,arr.length,i);
            }
            for(int i=arr.length-1;i>=0;i--){
        
                int t=arr[0];
                arr[0]=arr[i];
                arr[i]=t;
                getMaxHeap(arr,i,0);//i是下一次需要排序数组的长度，index为0是因为只调换了arr【0】和最后一位，现有的数组除了arr【0】以外一定满足大顶堆。
            }
    
    
    //        getMaxHeap(arr,arr.length,index);
        }
        private static void getMaxHeap(int[]arr,int size,int index){
        
            int leftIndex=index*2+1;
            int rightIndex=index*2+2;
            int maxIndex=index;
    
            if(leftIndex<size&&arr[maxIndex]<arr[leftIndex]){
        
                maxIndex=leftIndex;
            }
            if(rightIndex<size&&arr[maxIndex]<arr[rightIndex]){
        
                maxIndex=rightIndex;
            }
            if(index!=maxIndex){
        
                int t=arr[index];
                arr[index]=arr[maxIndex];
                arr[maxIndex]=t;
                getMaxHeap(arr,size,maxIndex);
            }
        }
    }

### 注意：小心角标越界。 ###

[堆排序讲解视频][Link 8]

[Link 1]: https://www.bilibili.com/video/BV1T4411A7Fy?p=7
[Link 2]: https://www.bilibili.com/video/BV1T4411A7Fy?p=8
[Link 3]: https://www.bilibili.com/video/BV1T4411A7Fy?p=9
[Link 4]: https://www.bilibili.com/video/BV1T4411A7Fy?p=11
[Link 5]: https://www.bilibili.com/video/BV1T4411A7Fy?p=10
[Link 6]: https://www.bilibili.com/video/BV1T4411A7Fy?p=12
[Link 7]: https://www.bilibili.com/video/BV1T4411A7Fy?p=13
[Link 8]: https://www.bilibili.com/video/BV1T4411A7Fy?p=14