排序算法：所有常见排序方法

Myth丶恋晨 2022-10-29 09:15 125阅读 0赞

## 排序算法 ##

###  O ( n 2 ) O(n^2) O(n2) ###

#### 冒泡排序 ####

void bubbleSort(int[] arr){ 
            for(int i = 0 ; i < arr.length ; i ++){ 
                for(int j = 0 ; j < arr.length - i - 1 ; j ++ ){ 
                    if(arr[j] > arr[j + 1]){ 
                        int mid = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = mid;
                    }
                }
            }
        }

#### 选择排序 ####

void selectSort(int[] arr){ 
            for(int i = 0 ; i < arr.length ; i ++){ 
                for(int j = i + 1; j < arr.length ; j ++){ 
                    if(arr[j] < arr[i]){ 
                        int mid = arr[i];
                        arr[i] = arr[j];
                        arr[j] = mid;
                    }
                }
            }
        }

#### 插入排序 ####

*  近乎有序的话可达到 O(n)

void insertSort(int arr[]){ 
            for(int i = 1 ; i < arr.length ; i ++){ 
                for(int j = i ; j > 0 ; j--){ 
                    if(arr[j] < arr[j - 1]){ 
                        int mid = arr[j];
                        arr[j] = arr[j - 1];
                        arr[j - 1] = mid;
                    }
                }
            }
        }

#### 希尔排序 ####

*  复杂度  O ( n 2 / 3 ) O(n^\{2/3\}) O(n2/3)

关键思想

*  进行排序的元素索引位置是 0、step、2step、3step …

void shellsort(int[] arr){ 
            for(int step = arr.length - 1 ;step >= 1 ; step /= 2){ 
                for(int i = step ; i <= arr.length - 1 ; i += step){ 
                    for(int j = i ; j >= step ; j -= step){ 
                        if(arr[j] < arr[j - step]){ 
                            int mid = arr[j];
                            arr[j] = arr[j - step];
                            arr[j - step] = mid;
                        }
                    }
                }
            }
        }

###  O ( n l o g n ) O(nlogn) O(nlogn) ###

#### 归并排序 ####

递归的终止

*  二分就是只有一个元素时终止

每次 return 都返回一个新数组

*  原数组只用来传值

归并过程的三个索引

*  右边数组的
 *  左边数组的
 *  归并后要返回的数组的

int[] mergeSort(int[] arr){ 
            return merge(arr , 0 , arr.length - 1);
        }
    
        private  int[] merge(int[] arr , int l , int r){ 
            // 明确递归终止
            //对于分治来说，比如分两段，那么终止条件一定是一段长度是 1；如果分三段，那么终止条件一定是该段长度 1 或者 2，否则还可再分
            if(r - l == 0 ){ 
                return new int[]{ arr[r]};
            }
    
    
            int mid = (l + r) / 2;
            int[] lArr = merge(arr , l , mid);
            int[] rArr = merge(arr , mid + 1 , r);
            int[] res = new int[r - l + 1];
    
            for(int i = 0 , lIndex = 0 , rIndex = 0; i < r - l + 1 ; i ++){ 
                if( rIndex >= rArr.length
                        || ( lIndex < lArr.length && lArr[lIndex] <= rArr[rIndex])){ 
                    res[i] = lArr[lIndex ++];
                }else { 
                    res[i] = rArr[rIndex ++];
                }
            }
    
            return res;
        }

#### 快排 ####

三个索引

*  要确定位置元素的索引
 *  区间右边的索引（代表比
 *  区间左边的索引

终止条件

*  while( lIdx <= rIdx)
 *  因为如果只有两个元素的话，那么 lIdx 就等于 rIdx 了
 *  因此目标元素的位置就是 rIdx（因为这种终止条件下， Idx 代表的是比 target 大的，所以其左边第一个才是<= target 的）

void quickSort(int[] arr){ 
            _quickSort(arr , 0 , arr.length - 1);
        }
    
        private static void _quickSort(int[] arr , int l , int r){ 
            if(l >= r){ 
                return;
            }
    
            int target = arr[l];
            int lIdx = l + 1 , rIdx = r;
            // 因为要让两个元素的也能进入，所以终止条件取 =，即：
            // lIdx 最终代表的 >= target 的
            // rIdx 是 < target 的或者是起始位置下一个
            while(lIdx <= rIdx){ 
                if(arr[lIdx] >= target){ 
                    while (arr[rIdx] > target && lIdx <= rIdx){ 
                        rIdx --;
                    }
                    if (lIdx > rIdx) { 
                        break;
                    }else { 
                        ArrUtil.swap(arr , lIdx , rIdx --);
                    }
                }
                lIdx ++;
            }
            ArrUtil.swap(arr , l  , rIdx);
    
            _quickSort(arr , l , rIdx - 1);
            _quickSort(arr , rIdx + 1 , r);
    
        }

#### 堆排序 ####

两个步骤

*  构建大堆
    
     *  从 i = 1 开始，i = arr.length 结束
     *  自底向上调整（只比较父节点就可以，因为只要保证每个节点增加时都比父节点小，那么就不用担心交换做了父节点后但比另一个兄弟小），保证父节点必须比两个子节点都大，不然就交换
 *  对大堆进行调整
    
     *  从后向前遍（即 i = arr.length - 1 开始），直到只剩一个元素（即 i = 1）结束
     *  把堆顶（即 index = 1，代表的最大元素）和最后的位置的元素交换
     *  重新调整堆（自顶向下调整，直到遇见父节点都比左右子节点大结束），然后又得到新的堆顶
     *  重复上面两步

void heapSort(int[] arr){ 
            // 构建大堆
            for(int i = 1;  i < arr.length ; i ++ ){ 
                int newDataIdx = i;
                int parent = newDataIdx / 2;
                while(parent >= 1 && arr[parent] < arr[newDataIdx]){ 
                    ArrUtil.swap(arr , parent , newDataIdx);
                    newDataIdx = parent;
                    parent /= 2;
                }
            }
    
            // 用大堆实现从小到大排序
            for(int i = arr.length - 1; i > 1 ; i --){ 
                ArrUtil.swap(arr , i , 1);
                int parent = 1;
                while (parent <= (arr.length - 1) /2
                        && (arr[parent * 2] > arr[parent] || arr[parent * 2 + 1] > arr[parent])){ 
                    int lchildIdx = parent * 2 < i ? parent * 2 : 0;
                    int rchildIdx = parent * 2 + 1 < i ? parent * 2 + 1 : 0;
                    int newParentIdx;
    
                    if( lchildIdx == 0){ 
                        break;
                    }else if(rchildIdx == 0){ 
                        newParentIdx = lchildIdx;
                    }else { 
                        newParentIdx = arr[lchildIdx] > arr[rchildIdx] ? lchildIdx : rchildIdx;
                    }
    
                    ArrUtil.swap(arr , newParentIdx , parent);
                    parent = newParentIdx;
                }
            }
    
    
        }

### O(n) ###

#### 计数排序 ####

*  仅适用于已知有多少种不同元素

思想

*  遍历一次，对每种的元素个数进行计数
 *  按每种元素的个数进行还原（例如 3个1、2个2，那么数组前三个放 1，后两个放 2）