七大排序算法

我会带着你远行 2024-03-27 15:22 62阅读 0赞

**目录**

1.直接插入排序

1.思想

2.特性

3.步骤

4.代码

2.希尔排序

1.思想

2.特性

3.步骤

4.代码

3.直接选择排序

1.思想

2.特性

3.步骤

4.代码

4.堆排序

2.特性

3.步骤

4.代码

5.冒泡排序

1.思想

2.特性

3.步骤

4.代码

6.快速排序

1.思想

2.特性

3.步骤

4.代码

7.归并排序

1.思想

2.特性

3.步骤

4.代码

--------------------

## 1.直接插入排序 ##

### 1.思想 ###

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列

### 2.特性 ###

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

b.空间复杂度：O(1)

c.稳定性：稳定

### 3.步骤 ###

1.从第二个开始，一个一个插入，每次插入都依次从后往前比较

2.插入的值小，则array\[j\]的值往后移一个

3.继续和前一个比较，直到插入的值大返回

4.插入的值赋给下标为j+1的位置

![4821beb71293407dbcebdc26a9100f77.png][]

### 4.代码 ###

public static void insertSort(int[] array){
            for (int i = 1; i < array.length; i++) {
                //插入一个tmp
                int tmp=array[i];
                //从下标为j的元素，开始一个一个往前比较
                int j=i-1;
                for(;j>=0;j--){
                    if(tmp<array[j]){
                        array[j+1]=array[j];
                    }else{
                        break;
                    }
                }
                array[j+1]=tmp;
            }
        }

## 2.希尔排序 ##

希尔排序法又称缩小增量法。

### 1.思想 ###

先选定一个整数，把待排序中所有分成多个组，对每一组进行排序，直到gap=1.

### 2.特性 ###

a.时间复杂度:O（N^1.3）-O(N^1.5)

b.空间复杂度:O（1）

c.稳定性:不稳定

d.希尔排序是对直接插入排序的优化，gap>1都是预排序

### 3.步骤 ###

先分组，在排序（排序方法与直接插入排序类似）

![de20f571412248268897ba5f89a9c40c.png][]

### 4.代码 ###

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

## 3.直接选择排序 ##

### 1.思想 ###

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

### 2.特性 ###

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

b.空间复杂度：O(1)

c.稳定性：不稳定

### 3.步骤 ###

1.从第一个开始和后面的每一个比较，找到最小值和第一个交换

2.继续从第二个开始比较，以此类推

![670d21aca6e94130aad3e1316b43a8a8.png][]

### 4.代码 ###

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

## 4.堆排序 ##

1.思想

排升序要建大堆，排降序建小堆

### 2.特性 ###

a.时间复杂度：O(N\*logN)

b.空间复杂度：O(1)

c.稳定性：不稳定

### 3.步骤 ###

1.创建大根堆

2.堆顶和最后一个交换，堆顶调整为大根堆，继续堆顶和倒数第二个交换

![c05ad220daee4568b30ec871ec840959.png][]

### 4.代码 ###

public static void heapSort(int[] array){
            creatBigHeap(array);
            int end= array.length-1;
            while(end>0){
                swap(array,0,end);
                shiftDown(array,0,end);
                end--;
            }
        }
        //创建大根堆
        public static void creatBigHeap(int[] array){
           for(int parent=(array.length-2)/2;parent>=0;parent--){
               shiftDown(array,parent,array.length);
           }
        }
        //向下调整
        private static void shiftDown(int[] array,int parent,int len){
           int child=2*parent+1;
           while(child<len){
               if(child+1<len && array[child]<array[child+1]){
                   child++;
               }
               if(array[child]>array[parent]){
                   swap(array,parent,child);
                   parent=child;
                   child=2*parent+1;
               }else{
                   break;
               }
           }
        }

## 5.冒泡排序 ##

### 1.思想 ###

根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

### 2.特性 ###

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

b. 空间复杂度：O(1)

c. 稳定性：稳定

### 3.步骤 ###

1.  比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.  对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.  针对所有的元素重复以上的步骤，除了最后一个。
4.  持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

### 4.代码 ###

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

## 6.快速排序 ##

### 1.思想 ###

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

### 2.特性 ###

a. 时间复杂度：O(N\*logN)

b. 空间复杂度：O(logN)

c. 稳定性：不稳定

### 3.步骤 ###

给定low 和high分别代表第一个元素和最后一个位置元素的索引，

假定基准值key是最左侧的元素，比较的时候从数组的尾部进行比较，

(1).当最右侧的元素大于基准值key的时候，high–.如果arr\[high\]<key的时候，就交换arr\[low\]和arr\[high\]的值。交换比较的方向，即从数组的头部low的位置向后扫描。

(2).如果arr\[low\]的值小于基准值key的话，low++，当arr\[low\]>=key的时候，交换arr\[low\]和arr\[high\]的值。再次交换比较的方向，数组从尾部high的位置从后往前扫描。

(3)不断重复1.2步，最终直到(low==high)的时候，low的位置就是该基准值在数组中的正确索引位置。

1.Hoare版

l找到比基准大的停下来 ，r找到比基准小的停下来,l和r交换

l和left交换

![8ae6ace069234624adea97afbb82999a.png][]

2.挖坑法

先将第一个数据存放在临时变量key中，形成一个坑位

![f7761d2daf744f4a9413777126213fb7.png][]

### 4.代码 ###

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

Hoare版

public static int partition(int[] array,int left,int right) {
            int i=left;
            int j=right;
            int pivot=array[left];
            while(i<j){
                while(i<j && array[j]>=pivot){
                    j--;
                }
                while(i<j && array[i]<=pivot){
                    i++;
                }
                swap(array,i,j);
            }
            swap(array,i,left);
            return i;
        }

挖坑法

public static int partition(int[] array,int left,int right){
            int tmp=array[left];
            while(left<right){
                while(left<right && array[right]>=tmp){
                    right--;
                }
                array[left]=array[right];
                while(left<right && array[left]<=tmp) {
                    left++;
                }
                array[right]=array[left];
            }
            array[left]=tmp;
            return left;
        }

## 7.归并排序 ##

### 1.思想 ###

即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表

### 2.特性 ###

a. 时间复杂度：O(N\*logN)

b. 空间复杂度：O(N)

c. 稳定性：稳定

### 3.步骤 ###

先分割，直到把每一个分完，然后根据大小合并

![40d1b0deb6af4255b21e79e0add6a1e0.png][]

### 4.代码 ###

public static void mergeSort(int[] array){                               
        mergeSortFunc(array,0, array.length-1);                               
     }                                                                        
     //分割                                                                     
     private static void mergeSortFunc(int[] array,int left,int right){       
         if(left>=right){                                                      
             return;                                                          
         }                                                                    
         int mid=(left+right)/2;                                              
         mergeSortFunc(array,left,mid-1);                                     
         mergeSortFunc(array,mid+1,right);                                    
         merge(array,left,right,mid);                                         
     }                                                                        
     //合并                                                                     
     private static void merge(int[] array,int start,int end,int mid){        
         int s1=start;                                                        
         int s2=mid+1;                                                        
         int[] tmp=new int[end-start+1];                                      
         int k=0;                                                             
         while(s1<=mid && s2<=end){                                           
             if(array[s1]<array[s2]){                                         
                 tmp[k++]=array[s1++];                                        
             }                                                                
             if(array[s1]>array[s2]){                                         
                 tmp[k++]=array[s2++];                                        
             }                                                                
                                                                              
         }                                                                    
         while(s1<=mid){                                                      
               tmp[k++]=array[s1++];                                          
         }                                                                    
         while(s2<=end){                                                      
             tmp[k++]=array[s2++];                                            
         }                                                                    
         for (int i = 0; i < tmp.length; i++) {                               
          array[i+start]=tmp[i];                                              
         }                                                                    
     }

##  ##

[4821beb71293407dbcebdc26a9100f77.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/0628a64bb7784668a0b51f78dc4391e0.png
[de20f571412248268897ba5f89a9c40c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/77f6be1eb0ef4e9d93055e28befd9619.png
[670d21aca6e94130aad3e1316b43a8a8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/bd775b63d4344e72907f9b3e841f7637.png
[c05ad220daee4568b30ec871ec840959.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/61afb30e199d452b9732ac640c5aa895.png
[8ae6ace069234624adea97afbb82999a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/473f9f9de52c4a84b24375296e934568.png
[f7761d2daf744f4a9413777126213fb7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/ad8dcf9b6459406aa492a35ebbae1a3d.png
[40d1b0deb6af4255b21e79e0add6a1e0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/484241659866475190e6d5ca117fb2ae.png