面试题总结——七大排序

梦里梦外; 2023-05-22 04:59 2阅读 0赞

## 面试题总结——七大排序 ##

###  时间复杂度 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70]

###  冒泡排序 ###

private static void bubbleSort(int[] array) {
            for (int i = 0; i < array.length - 1; i++) {   
                boolean flag = true;
                for (int j = 0; j < array.length - i - 1; j++) {
                    if (array[j] > array[j + 1]) {
                        int tmp = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = tmp;
                        flag = false;
                    }
                }
                if (flag) {
                    break;
                }
            }
        }

###  快速排序 ###

private static void quickSort(int[] array) {
            quick(array, 0, array.length - 1);
        }
    
        private static void quick(int[] array, int start, int end) {
    	    if (end - start + 1 < 16) {
    	        insertSort(array, start, end);
    	    }
            medianOfThree(array, start, end);
            int par = portion(array, start, end);
            if (par > start + 1) {
                quick(array, start, par - 1);
            }
            if (par < end - 1) {
                quick(array, par + 1, end);
            }
        }
        
    	private static int portion(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] = array[high];
                } else {
                    break;
                }
    
                while (low < high && array[low] <= tmp) {
                    low++;
                }
                if (low < high) {
                    array[high] = array[low];
                }
            }
            array[low] = tmp;
            return low;
        }
    
    	private static void medianOfThree(int[] array, int low, int high) {
            int mid = (low + high) / 2;
            if (array[mid] > array[high]) {
                int tmp = array[mid];
                array[mid] = array[high];
                array[high] = tmp;
            }
            if (array[low] > array[high]) {
                int tmp = array[low];
                array[low] = array[high];
                array[high] = tmp;
            }
    
            if (array[low] < array[mid]) {
                int tmp = array[low];
                array[low] = array[mid];
                array[mid] = tmp;
            }
        }
    
    	private static void insertSort(int[] array, int start, int end) {
            for (int i = start + 1; i <= end; i++) {
                int j = i - 1;
                int tmp = array[i];
                while (j >= start && array[j] > tmp) {
                    array[j + 1] = array[j];
                    j--;
                }
                array[j + 1] = tmp;
            }
        }

###  选择排序 ###

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

###  直接插入排序 ###

private static void insertSort(int[] array) {
            for (int i = 1; i < array.length; i++) {
                int j = i - 1;
                int tmp = array[i];
                while (j >= 0 && array[j] > tmp) {
                    array[j + 1] = array[j];
                    j--;
                }
                array[j + 1] = tmp;
            }
        }

###  堆排序 ###

private static void heapSort(int[] array) {
            // 初始化堆，先找到最后一个根节点
            for (int i = array.length / 2 - 1; i >= 0; i--) {
                adjustDown(array, array.length, i);
            }
            // 从最后一个结点向前，与根节点进行交换，并对根节点进行向下调整
            for (int i = array.length-1; i > 0; i--) {
                int tmp = array[i];
                array[i] = array[0];
                array[0] = tmp;
                // i后面都是调整好了的，所以缩减树的容量
                // i刚好代表当前树的length，array[i]已经和array[0]交换了，已经是最大的了
                // 此时不会再取到array[i]了，因此把i直接当length即可，代替写array.length
                adjustDown(array,i,0);
            }
        }
    	
    	private static void adjustDown(int[] array, int length, int i) {
            int parent = i;
            // child代表的是两个子节点中较大的那一个，先将其设置为左子节点
            int child = parent * 2 + 1;
            while (child < length) {
                if (child + 1 < length && array[child + 1] > array[child]) {
                    child++;
                }
                // 比较当前子节点中较大的值和根节点值的大小关系
                if (array[child] > array[parent]) {
                    // 交换子节点和根节点
                    int tmp = array[child];
                    array[child] = array[parent];
                    array[parent] = tmp;
    
                    // 由于向下调整之后可能会导致下面的树出现问题，因此需要一直向下遍历
                    // 直到child>=length为止
                    parent = child;
                    child = parent*2+1;
                } else {
                    // 如果当前节点子节点的值比根节点小，则说明已经是大根堆了，直接break
                    break;
                }
            }
        }

###  归并排序 ###

private static void mergeSort(int[] array, int start, int end, int[] tmpArray) {
            if (start >= end) {
                return;
            }
            int mid = (start + end) / 2;
            mergeSort(array, start, mid, tmpArray);
            mergeSort(array, mid + 1, end, tmpArray);
            merge(array, start, mid, end, tmpArray);
        }
    
    	private static void merge(int[] array, int start, int mid, int end, int[] tmpArray) {
    		// 尽量不要再递归的过程中创建数组(尤其是这么大的数组)
            int tmpIndex = start;
            int s2 = mid + 1;
            // 先保存一下start的值，后面会用到
            int oldStart = start;
    
            // 保证有两个归并段
            while (start <= mid && s2 <= end) {
                // 若array[start] == array[s2]，则先将start对应的值加入到辅助数组中
                // 由于start<s2，排序前array[start]在array[s2]前
                // 而排序后，array[start]依旧在array[s2]前
                // 因此，归并排序是稳定的
                if (array[start] <= array[s2]) {
                    tmpArray[tmpIndex++] = array[start++];
                } else {
                    tmpArray[tmpIndex++] = array[s2++];
                }
            }
    
            // 以下两个while对应上面while跳出的三种可能性
            //      1、start>mid
            //      2、根本没进上面的循环(只有一个归并段)
            //      3、s2>end
    
            // 若第一个归并段[start,mid]还没走完，或者s2越界，只有第一个归并段的情况
            while (start <= mid) {
                tmpArray[tmpIndex++] = array[start++];
            }
            // 若第二个归并段[s2,end]还没走完
            while (s2 <= end) {
                tmpArray[tmpIndex++] = array[s2++];
            }
    
            // 将tmp中的内容复制到array中
            // 此时必须使用循环一个一个对元素进行赋值，而不能用一些复制函数(Arrays.copyOf()..)
            // 因为此处的array只是一个数组的引用，如果使用复制函数相当于是改变了形参array的引用
            // 而指向了另一块与tmpArray元素完全相同的存储地址
            for (int i = oldStart; i <= end; i++) {
                array[i] = tmpArray[i];
            }
        }

###  希尔排序 ###

// 跳跃间隔式的排序
    	private static void shellSort(int[] array) {
            int[] drr = {5, 3, 1};
            for (int i = 0; i < drr.length; i++) {
                shell(array, drr[i]);
            }
        }
    
    	private static void shell(int[] array, int gap) {
            for (int i = gap; i < array.length; i++) {
                int j = i - gap;
                int tmp = array[i];
                while (j >= 0 && array[j] > tmp) {
                    array[j + gap] = array[j];
                    j -= gap;
                }
                array[j + gap] = tmp;
            }
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70]: /images/20230521/a9f52e2edf124cb7a575ad1ea267752f.png