数据结构七大排序解读（java版）

桃扇骨 2023-06-02 09:28 3阅读 0赞

\*\*

## 排序 ##

\*\*  
一般默认的排序是升序的顺序  
下边用到的主函数（另外写了一个类），交换函数和打印函数分别是

public class testDemo { 
        public static void main(String[] args) { 
            mySort testSort=new mySort();
            int[] array={ 8,11,2,4,6,3,7,1};
          /* testSort.insertSort(array); testSort.show(array); testSort.shellSort(array); testSort.show(array); testSort.selectSort(array); testSort.show(array); testSort.heapSort(array); testSort.show(array); testSort.quickSort(array); testSort.show(array); testSort.bubbleSort(array); testSort.show(array);*/
            testSort.mergeSort(array);
            testSort.show(array);
        }
    }

//交换
        void swap(int[] array,int a,int b){ 
            int tmp=array[a];
            array[a]=array[b];
            array[b]=tmp;
        }
        //打印
        void show(int[] array){ 
            for(int i=0;i<array.length;i++){ 
                System.out.print(array[i]+" ");
            }
            System.out.println();
        }

**一.插入排序：**  
1.直接插入排序：每次选择无序区间的第一个元素，在有序区间内选择合适的位置插入，直到整体有序。

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

性能分析：  
![在这里插入图片描述][20191004160400181.png]  
当数据越接近有序的时候它的效率就越高

2.希尔排序：也是直接插入排序的优化版（主要是让数据接近有序）。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所 有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1 时，所有记录在统一组内排好序。

//希尔排序(优化版的插入排序)
        void shellSort(int[] array){ 
            int gap=array.length;
            while(gap>1){ 
                insertSortGap(array,gap);
                gap=(gap/3)+1;
            }
            if(gap==1){ 
                insertSortGap(array,gap);
            }
        }
        //希尔排序的原理
        void insertSortGap(int[] array,int gap){ 
            for (int i = 1; i < array.length; i++) { 
                int tmp = array[i];
                int j;
                for (j = i - gap; j >= 0; j-=gap) { 
                    if (array[j] > tmp) { 
                        array[j + gap] = array[j];
                    } else { 
                        break;
                    }
                }
                array[j + gap] = tmp;
            }
        }

性能分析：  
![在这里插入图片描述][20191004160606928.png]  
**二.选择排序**

3.直接选择排序：每一次从无序区间选出最大（或最小）的一个元素，存放在无序区间的最后（或最前），直到全部待排序的数据元素排完 。

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

性能分析：  
![在这里插入图片描述][20191004161233650.png]  
4.堆排序：排升序要建大堆；排降序要建小堆。

//堆排序(排升序建大堆，排降序建小堆)(所以整体的时间复杂度为O(nlog2^n)，空间复杂度为O(1))
        void heapSort(int[] array){ 
            creatHeap(array);
            for(int j=0;j<array.length-1;j++){ 
                swap(array,0,array.length-1-j);
                shiftDown(array,0,array.length-1-j-1);
                //这里end:array.length-1-j-1还要减一是因为上面已经发生了交换，不算做下一次调整的结尾
            }
        }
        //建堆(时间复杂度为n/2)
        private void creatHeap(int[] array){ 
            for(int i=(array.length-1-1)/2;i>=0;i--){ 
                shiftDown(array,i,array.length-1);
            }
        }
        //向下调整(负责把每一颗子树调整为大根堆)(时间复杂度为log2^n)
        private void shiftDown(int[] array,int start,int end){ 
            int tmp=array[start];
            for(int i=2*start+1;i<=end;i=2*i+1){  //i<end 时说明它有左右孩子
                if((i<end)&&array[i]<array[i+1]){ 
                    i++;   //i保存的是最大值的下标
                }
                if(array[i]>tmp){ 
                    array[start]=array[i];
                    start=i;
                }else{ 
                    break;
                }
            }
            array[start]=tmp;
        }

性能分析：  
![在这里插入图片描述][20191004162022697.png]  
**三.交换排序**

5.冒泡排序：在无序区间，通过相邻数的比较，将最大的数冒泡到无序区间的最后，持续这个过程，直到数组整体有序。

//冒泡排序
        void bubbleSort(int[] array){ 
            for(int i=0;i<array.length;i++){ 
                for(int j=0;j<array.length-i-1;j++){ 
                    if(array[j]>array[j+1]){ 
                        swap(array,j,j+1);
                    }
                }
            }
        }

性能分析：  
![在这里插入图片描述][20191004162750168.png]  
6.快速排序：（1）从待排序区间选择一个数，作为基准值(pivot)； （2）Partition: 遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的 （可以包含相等的）放到基准值的右边； （3）采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间的长度 == 1，代表已经有序，或者小区间的长度 == 0，代表没有数据。

//快速排序
        void quickSort(int[] array){ 
            quick(array,0,array.length-1);
        }
        void quick(int[] array,int low,int high){ 
            if(low==high){ 
                return;
            }
            if(high-low+1<=10){ 
                insertSort1(array,low,high);
            }
            //takeThreeNumber(array,high,low);
            int par =partion(array,low,high);
            //递归左边
            if(par>low+1){   //为了保证此时左边有两个数据以上
                quick(array,low,par-1);
            }
            //递归右边
            if(par+1<high){    //为了保证此时右边有两个数据以上
                quick(array,par+1,high);
            }
        }
        //快速排序优化方式1：三数取中法:预防给的数据本来是有序的,可以减少栈溢出的概率，效率也会提很多
        void takeThreeNumber(int[] array,int low,int high){ 
            int mid=(low+high)>>>1;  //这里是无符号数右移一位
            if(array[mid]>array[low]){ 
                swap(array,mid,low);
            }
            if(array[mid]>array[high]){ 
                swap(array,mid,high);
            }
            if(array[low]>array[high]){ 
                swap(array,low,high);
            }
            //这三个if下来就可以达到array[mid]<=array[low]<=array[high],然后再用partion
        }
        //快速排序优化方式2：在low和high之间的数据低于一个数值时，做直接插入排序
        void insertSort1(int[] array,int low,int high){ 
            for (int i = low+1; i <high+1; i++) { 
                int tmp = array[i];
                int j;
                for (j = i - 1; j >= 0; j--) { 
                    if (array[j] > tmp) { 
                        array[j + 1] = array[j];
                    } else { 
                        break;
                    }
                }
                array[j + 1] = tmp;
            }
        }
        //快速排序原理1(Hoare法)
        int partion(int[] array,int low,int high){ 
            int i=low;
            int j=high;
            int par=array[low];
                while(i<j&&array[j]>par){ 
                    j--;
                }
                while(i<j){ 
                    while(i<j&&array[i]<par){ 
                        i++;
                    }
                swap(array,i,j);
            }
            swap(array,i,low);
            return i;
        }
        //快速排序原理2(挖坑法)
        int partion1(int[] array,int low,int high){ 
            int tmp=array[low];
            while(low<high){ 
                while((low<high)&&array[high]>=tmp){ 
                    high--;
                }
                if(low==high){ 
                    //array[low]=tmp;
                    break;
                }else{ 
                    array[low]=array[high];
                }
                while((low<high)&&array[low]<=tmp){ 
                    low++;
                }
                if(low==high){ 
                    //array[low]=tmp;
                    break;
                }else{ 
                    array[high]=array[low];
                }
            }
            array[low]=tmp;
            return low;
        }
        //快速排序原理3(前后遍历法)
        int partion2(int[] array,int low,int high){ 
            int j=low+1;
            int tmp=array[low];
            for(int i=low+1;i<=high;i++){ 
                if(array[i]<tmp){ 
                    swap(array,i,j);
                    j++;
                }
            }
            swap(array,j-1,low);
            return j-1;
        }

性能分析：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70]  
优化总结：1. 选择基准值很重要，通常使用几数取中法  
2. partition 过程中把和基准值相等的数也选择出来  
3. 待排序区间小于一个阈值时（例如 48），使用直接插入排序

**四.归并排序**

7.归并排序：该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使 子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

//归并排序
        void mergeSort(int[] array){ 
            mergeSortInter(array,0,array.length);
        }
        void mergeSortInter(int[] array,int low,int high){ 
            if(low+1>=high){ 
                return;
            }
            int mid=(low+high)/2;
            mergeSortInter(array,low,mid);
            mergeSortInter(array,mid,high);
            merge(array,low,mid,high);
        }
        //归并排序原理
        /** 下边的merge1方法是错误的，和下边唯一的区别是下边用了i,j来代替low,high，上边错误的原因是中间low和high 会发生变化导致错误 */
        /* void merge1(int[] array,int low,int mid,int high){ int[] extra=new int[high-low]; int k=0; while(low<mid&&mid<high){ if(array[low]<=array[mid]){//加入了等于，为了保证稳定性 extra[k++]=array[low++]; }else{ extra[k++]=array[mid++]; } } while(low<mid){ extra[k++]=array[low++]; } while(mid<high){ extra[k++]=array[mid++]; } for(int t=0;t<high-low;t++){ array[low+t]=extra[t]; } }*/
        void merge(int[] array,int low,int mid,int high){ 
            int[] extra=new int[high-low];
            int k=0;int i=low;int j=mid;
            while(i<mid&&j<high){ 
                if(array[i]<=array[j]){   //加入了等于，为了保证稳定性
                    extra[k++]=array[i++];
                }else{ 
                    extra[k++]=array[j++];
                }
            }
            while(i<mid){ 
                extra[k++]=array[i++];
            }
            while(j<high){ 
                extra[k++]=array[j++];
            }
            for(int t=0;t<high-low;t++){ 
                array[low+t]=extra[t];
            }
        }

性能分析：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70 1]  
优化总结：在排序过程中重复利用两个数组，减少元素的复制过程

**五.排序总结**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70 3]

[20191004160400181.png]: /images/20230601/2b3c98f6cb9b46718bbd68f2ba040a7d.png
[20191004160606928.png]: /images/20230601/5a780c7a07474ece81154ceee9028051.png
[20191004161233650.png]: /images/20230601/4e5fb3ded0bd47b0b3c5548657f15bab.png
[20191004162022697.png]: /images/20230601/58fe5478458048aab93c0eb99434e0c2.png
[20191004162750168.png]: /images/20230601/f50a558a7c36462795bf5ccd4bb05fc4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70]: /images/20230601/9d0aef50acde4cb8b84e0c8605d82b0b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70 1]: /images/20230601/9ba24c8c7de6427d94360ee361a5d0d5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70 2]: /images/20230601/e0bef6ee04584bac8e49c833efca4a6a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70 3]: /images/20230601/b9b1bb9e13f54e5a8045d580625995ca.png