（Java版）八大排序算法（希尔排序，快速排序，堆排序等）

清疚 2022-10-16 07:54 161阅读 0赞

**目录**

一.冒泡排序

二.选择排序

三.插入排序

四.希尔排序

五.快速排序

六.归并排序

七.堆排序

八.基数排序

九.排序算法总结（时间复杂度，稳定性等）

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

# 一.冒泡排序 #

基本思想：

1.  先比较第1个数和第2个数的大小，进行交换操作，把大的数放在后边；
2.  在比较第2个数和第3个数的大小，进行交换操作，把大的数放在后边；
3.  先比较第3个数和第4个数的大小，进行交换操作，把大的数放在后边；
4.  ......
5.  最后比较第n-1个数和第n个数的大小，进行交换操作，把大的数放在后边（此时数组末尾的数就是整个数组中最大的数）。
6.  重复上述1-5步骤（重复第1次时，末尾第1个数不进行上述操作；重复第2次时，末尾第2个数不进行上述操作；......）

代码实现：

/*
     * 冒泡排序
     * 分类 -------------- 内部比较排序
     * 数据结构 ---------- 数组
     * 最差时间复杂度 ---- O(n^2)
     * 最优时间复杂度 ---- 如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n)
     * 平均时间复杂度 ---- O(n^2)
     * 所需辅助空间 ------ O(1)
     * 稳定性 ------------ 稳定
     */
    public static void bubbleSort(int[] arr){
            for(int i = 0; i < arr.length-1;i++){//冒泡的趟数，n个数冒n-1次即可
                boolean flag = true;
                for(int j = 0; j < arr.length-1-i;j++){//每趟两个数比较的次数
                    if (arr[j] > arr[j+1]){
                        flag = false;
                        int temp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = temp;
                    }
                }
                if (flag){//如果内循环没有执行过，则arr已经有序
                    break;
                }
            }
    }

# 二.选择排序 #

基本思想：

1.  先比较第1个数和第2个数的大小，用临时变量记住较小值的下标；
2.  在比较第2个数和第3个数的大小，用临时变量记住较小值的下标；
3.  ......
4.  最后比较第n-1个数和第n个数的大小，用临时变量记住较小值的下标；
5.  此时把arr\[0\]与这个arr\[下标\]进行交换（此时数组的第1个数就是最小的）
6.  \---------------------------------------------------------------------------------------------------------
7.  在比较第2个数和第3个数的大小，用临时变量记住较小值的下标；
8.  在比较第3个数和第4个数的大小，用临时变量记住较小值的下标；
9.  ......
10. 最后比较第n-1个数和第n个数的大小，用临时变量记住较小值的下标；
11. 此时把arr\[1\]与这个arr\[下标\]进行交换（此时数组的第2个数就是最小的）。

*  重复上述步骤即可

代码实现：

/**
     * 选择排序
     * 分类 -------------- 内部比较排序
     * 数据结构 ---------- 数组
     * 最差时间复杂度 ---- O(n^2)
     * 最优时间复杂度 ---- 如果序列在一开始已经大部分排序过的话,会接近O(n)
     * 平均时间复杂度 ---- O(n^2)
     * 所需辅助空间 ------ O(1)
     * 稳定性 ------------ 稳定
     */
    public static void selectSort(int[] arr){
            for(int i = 0;i < arr.length-1;i++){//总共的趟数
                int minIndex = i;//记录一趟中最小值的下标
                for(int j = i+1;j<arr.length;j++){
                    if(arr[j] < arr[minIndex]){
                        minIndex = j;//更新minIndex
                    }
                }
                if (minIndex != i){// 交换值(如果minIndex更新了)
                    int temp = arr[minIndex];
                    arr[minIndex] = arr[i];
                    arr[i] = temp;
                }
            }
    }

# 三.插入排序 #

基本思想：

1.  第一个元素可以认为已经被排序；
2.  取出下一个元素，在已经排序的元素序列中从后向前扫描
3.  如果该元素（已排序）大于新元素，将该元素（已排序）后移一位
4.  重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5.  将新元素插入到该位置后面
6.  重复步骤2~5

代码实现：

/**
     * 插入排序
     * 分类 ------------- 内部比较排序
     * 数据结构 ---------- 数组
     * 最差时间复杂度 ---- 最坏情况为输入序列是降序排列的,此时时间复杂度O(n^2)
     * 最优时间复杂度 ---- 最好情况为输入序列是升序排列的,此时时间复杂度O(n)
     * 平均时间复杂度 ---- O(n^2)
     * 所需辅助空间 ------ O(1)
     * 稳定性 ------------ 稳定
     */
    public static void insertSort(int[] arr){
            for(int i = 1;i < arr.length;i++){
                int insertVal = arr[i];//需要进行插入的数
                int insertIndex = i-1;//已排好序的末尾元素的下标
                while (insertIndex >= 0 && insertVal < arr[insertIndex]){
                    arr[insertIndex+1] = arr[insertIndex];//后移
                    insertIndex--;
                }
                if (insertIndex != i-1){//如果不是原位置,则插入到已排序的末尾，，，否则不插入
                    arr[insertIndex+1] = insertVal;
                }
            }
    }

# 四.希尔排序 #

基本思想：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yeHVhbnNoZW4_size_16_color_FFFFFF_t_70][]

代码实现：

/**
     * 希尔排序
     * 分类 -------------- 内部比较排序
     * 数据结构 ---------- 数组
     * 最差时间复杂度 ---- 根据步长序列的不同而不同。已知最好的为O(n(logn)^2)
     * 最优时间复杂度 ---- O(n)
     * 平均时间复杂度 ---- 根据步长序列的不同而不同。
     * 所需辅助空间 ------ O(1)
     * 稳定性 ------------ 不稳定
     */
    public static void shellSort(int[] arr){
    		for(int gap = arr.length/2; gap > 0; gap /=2){//gap增量
    			//按照增量进行分组（共gap组），然后分别进行插入排序
    			for (int i = gap;i < arr.length ;i++){
    				for (int j = i-gap; j >= 0; j -= gap){
    					if (arr[j] > arr[j+gap]){
    						int temp = arr[j];
    						arr[j] = arr[j+gap];
    						arr[j+gap] = temp;
    					}
    				}
    			}
    		}
    }

# 五.快速排序 #

基本思想：

1.  选取一个基准值，然后让数组左边的值都比这个数小，右边的数比这个数大；
2.  然后左边数组和右边数组分别进行第1步
3.  如此往复......

代码实现：

/**
     * 分类 ------------ 内部比较排序
     * 数据结构 --------- 数组
     * 最差时间复杂度 ---- 每次选取的基准都是最大（或最小）的元素，导致每次只划分出了一个分区，需要进行n-1次划分才能结束递归，时间复杂度为O(n^2)
     * 最优时间复杂度 ---- 每次选取的基准都是中位数，这样每次都均匀的划分出两个分区，只需要logn次划分就能结束递归，时间复杂度为O(nlogn)
     * 平均时间复杂度 ---- O(nlogn)
     * 所需辅助空间 ------ 主要是递归造成的栈空间的使用(用来保存left和right等局部变量)，取决于递归树的深度，一般为O(logn)，最差为O(n)      
     * 稳定性 ---------- 不稳定
     */
    public static void kuaiPai(int[] arr,int left,int right){
    		int l = left;
    		int r = right;
    		int pivot = arr[(left+right)/2];
    		while (l < r){
    			while (arr[l] < pivot){
    				l++;
    			}
    			while (arr[r] > pivot){
    				r--;
    			}
    			if (l >= r){
    				break;
    			}
    			int temp = arr[l];
    			arr[l] = arr[r];
    			arr[r] = temp;
    			if (arr[l] == pivot){
    				r--;
    			}
    			if (arr[r] == pivot){
    				l++;
    			}
    		}
    		if (l == r){
    			l++;
    			r--;
    		}
    		if (l < right){
    			kuaiPai(arr, l, right);
    		}
    		if (r > left){
    			kuaiPai(arr, left, r);
    		}
    }

# 六.归并排序 #

基本思想：

归并排序算法主要依赖归并操作。归并操作指的是将两个已经排序的序列合并成一个序列的操作，归并操作步骤如下：

1.  申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2.  设定两个指针，最初位置分别为两个已经排序序列的起始位置
3.  比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4.  重复步骤3直到某一指针到达序列尾
5.  将另一序列剩下的所有元素直接复制到合并序列尾

代码实现：

/**
     * 分类 -------------- 内部比较排序
     * 数据结构 ---------- 数组
     * 最差时间复杂度 ---- O(nlogn)
     * 最优时间复杂度 ---- O(nlogn)
     * 平均时间复杂度 ---- O(nlogn)
     * 所需辅助空间 ------ O(n)
     * 稳定性 ------------ 稳定
     */
    public static void mergeSort(int[] arr, int left, int right) {
       int mid = (left + right) / 2;
       if (left < right) {
          //左边递归
          mergeSort(arr, left, mid);
          //右边递归
          mergeSort(arr, mid + 1, right);
          //归并操作
          merge(arr, left, mid, right);
       }
    }
    
    public static void merge(int[] arr, int left, int mid, int right) {
       int[] temp = new int[right-left+1];
       int i = left;//左指针
       int j = mid + 1;//右指针
       int t = 0;
       while (i <= mid && j <= right) {//把较小的数移动到新数组中
          if (arr[i] < arr[j]) {
             temp[t++] = arr[i++];
          } else {
             temp[t++] = arr[j++];
          }
       }
       while (i <= mid) {// 将左边剩余元素填充进temp中
          temp[t++] = arr[i++];
       }
       while (j <= right) {// 将右序列剩余元素填充进temp中
          temp[t++] = arr[j++];
       }
       for(int k = 0 ; k < temp.length ; k++){//把新数组的数覆盖到原数组
          arr[left+k] = temp[k];
       }
    }

# 七.堆排序 #

基本思想：

1.  将待排序序列构造成一个大顶堆
2.  此时，整个序列的最大值就是堆顶的根节点。
3.  将其与末尾元素进行交换，此时末尾就为最大值。
4.  然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。
5.  如此反复执行，便能得到一个有序序列了。

代码实现：

**
     * 分类 -------------- 内部比较排序
     * 数据结构 ---------- 数组
     * 最差时间复杂度 ---- O(nlogn)
     * 最优时间复杂度 ---- O(nlogn)
     * 平均时间复杂度 ---- O(nlogn)
     * 所需辅助空间 ------ O(1)
     * 稳定性 ------------ 不稳定
     */
    public static void duipaixu(int[] arr){
            for (int i = arr.length/2-1; i >= 0;i--){//arr.length/2-1是一个非叶子节点
                fuzhu(arr, i, arr.length-1);
            }
            for (int i = arr.length-1 ; i > 0;i--){
                int temp = arr[0];
                arr[0] = arr[i];
                arr[i] = temp;
                fuzhu(arr, 0, i-1);//去掉最后一个元素，剩下的元素继续变形为一个最大堆
            }
    }
    
    
    public static void fuzhu(int[] arr,int start,int end){
            int temp = arr[start];
            int lIndex = 2*start +1;
            int nowIndex = start;
            for (;lIndex <= end;nowIndex=lIndex,lIndex=2*lIndex+1){
                if (lIndex < end && arr[lIndex] < arr[lIndex+1]){//让lIndex成为左右孩子节点较大值的下标
                    lIndex++;
                }
                if (temp >= arr[lIndex]){//如果当前节点的值 >= 其左右孩子节点的值，则局部最大堆成立，退出循环
                    break;
                }else {//让孩子节点与当前节点交换值
                    arr[nowIndex] = arr[lIndex];
                    arr[lIndex] = temp;
                }
    
            }
            
    }

# 八.基数排序 #

基本思想：

**连载中...**

代码实现：

**连载中...**

# 九.排序算法总结（时间复杂度，稳定性等） #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yeHVhbnNoZW4_size_16_color_FFFFFF_t_70 1][]