七种常见排序算法

秒速五厘米 2022-03-09 09:17 253阅读 0赞

以前欠下的基础，现在补

### 常用排序算法 ###

*   *  冒泡排序
     *  选择排序
     *  插入排序
     *  Shell排序
     *  快速排序
     *  堆排序
     *  归并排序

算法)

此图片来自网络 [https://blog.csdn.net/u012102104/article/details/79773907][https_blog.csdn.net_u012102104_article_details_79773907]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70]

## 冒泡排序 ##

冒泡排序的基本思路就是交换顺序，以从小到大排为例子，从数组尾部对数组中的数据依次比较大小，若右侧数据比左侧的小则交换位置，这么一来经过第一轮的排序后就可以选出最小的数字。冒泡排序对n个随机数的排序需要执行n-1次，效率较低。可以做个简单的优化：因为每一次循环都会选出当前循环中最小的数字并移动到左侧，所以第一次排序结束选出了最小的数字，第二次排序选出了第二小的数字，以此类推，那么前几次循环选出的最小数就无需再进行循环比较了。

/** * @param ：[numbers]待排序数组 * @return ：void * @throws : * @方法名： bubbleSort2 * @功能：冒泡排序数组 * @作者：2019/3/12 * @修改者: */
        public void bubbleSort2(int[] numbers) { 
            int length = numbers.length;
            int num1;
            //执行次数为n-1次
            for (int i = 0; i < length - 1; i++) { 
                //从尾部开始比较,每次循环选出循环中最小的一个数放在开头，
                // 所以随着次数的增加，比较的次数也越来越少
                for (int j = length - 1; j > i; j--) { 
                    //交换顺序
                    if (numbers[j] < numbers[j - 1]) { 
                        num1 = numbers[j];
                        numbers[j] = numbers[j - 1];
                        numbers[j - 1] = num1;
                    }
                }
            }
        }

## 选择排序 ##

选择排序的基本思路也是交换顺序

*  第一步从n个数中选出最小的数字和第一个数字（索引为0）的进行交换
 *  第二步从第二个数字（索引为1）的开始向后寻找最小的数字并和第二个数字（索引为1）进行交换，如此循环n-1次。可见效率也不高。优化方案和冒泡排序相同

/** * @param ：[numbers]待排序数组 * @return ：void * @throws : * @方法名： selectionSort2 * @功能：选择排序算法 * @作者：2019/3/12 * @修改者: */
        public void selectionSort2(int[] numbers) { 
            int length = numbers.length;
            int num1,k = 0;
            //循环n-1次
            for (int i = 0; i < length - 1; i++) { 
                num1 = numbers[i];
                for (int j = i; j < length; j++) { 
                    if (num1 > numbers[j]) { 
                        num1 = numbers[j];
                        //在选出最小值之前没必要每一次都进行换位操作，变量k为记录当前最小数的下标
                        k = j;
                    }
                }
                //只有在找出最小数才需要进行换位，所以需要判断k
                if (k != 0) { 
                    numbers[k] = numbers[i];
                    numbers[i] = num1;
                }
            }
        }

## 插入排序 ##

插入排序通过对未排序的数据逐个插入至合适的位置而完成排序工作，步骤如下：

*  将数组前两个数字进行排序
 *  num1 = arr\[ 2 \] 第三个数字和前一个数字进行对比，若num1 > arr\[ 1 \]则不变continue进入下一个循环（因为前两个已经排好顺序比比最后的大那就一定比之前的都大），若num1 < arr\[ 1 \]则arr\[ 2 \] = arr\[ 1 \]，继续比较num1和arr\[ 0 \]，若num1 > arr\[ 0 \]则arr\[ 2 \] = num1进入下一个循环，以此类推。

/** * @param ：[numbers]待排序数组 * @return ：void * @throws : * @方法名： insertionSort2 * @功能：插入排序 * @作者：2019/3/12 * @修改者: */
        public void insertionSort2(int[] numbers) { 
            int num1;
            int len;
            //执行n-1次
            for (int i = 1; i < numbers.length; i++) { 
                num1 = numbers[i];
                //len指针指向当前数字的前一个数字
                len = i - 1;
                while (len >= 0 && num1 < numbers[len]) { 
                    numbers[len + 1] = numbers[len];
                    //指针向左移动
                    len--;
    
                }
                //因为最后会多减1
                numbers[len + 1] = num1;
            }
        }

## Shell排序 ##

Shell排序是基于插入排序的思想，在处理大而散乱的数据时会比插入排序更快，因为插入排序在对有序数组进行排序时效率会更高，shell排序正是利用了这个特点。

*  首先将n个数字的数组分成n/2个数字序列，第1个数字和第n/2 + 1个数字为一组
 *  一次循环中将每个数字序列比较大小交换顺序
 *  进行下一次循环此时分成n/4个序列，再进行比较大小交换顺序，以此类推
 *  直到两个数字之间步长为1时即为插入排序

/** * @方法名： shellSort2 * @param ：[numbers] * @return ：void * @功能：shell排序 * @exception : * @作者：2019/3/12 * @修改者: */
        public void shellSort2(int[] numbers) { 
            //步长
            int step,num1,len;
            //控制循环次数
            for (int i = numbers.length/2; i > 0; i/=2) { 
                step = i;
                for (int j = i; j < numbers.length; j++) { 
                    num1 = numbers[j];
                    len = j - i;
                    while (len >= 0 && num1 < numbers[len]) { 
                        numbers[j] = numbers[len];
                        numbers[len] = num1;
                        len -= step;
                        j -= step;
                    }
                }
            }
        }

## 快速排序 ##

顾名思义真的很快…但是他是不稳定的算法，最坏的情况下速度和冒牌排序是相同的时间复杂度，一般可以使用三点取中法来优化分界值( base )的选定。

*  三数取中，取出头，中，尾三个数字，将最大的放在尾部，最小的放在中间，中间大小的放在开头，并将中间值赋值给变量Base
 *  将指针left和right分别对向数组的最左侧和最右侧，从数组右侧向左找比base小的值找到后赋值给左侧left指针指向的值，right指针停止移动，left指针开始向右移动寻找比base大的值放在右侧right指针指向的值。如此循环直到left和right相遇，将left = right时指向的数字设置为base。接着将两侧的数据递归调用此循环

/** * @param ：[numbers待排序数组, low低位, height高位] * @return ：void * @throws : * @方法名： quickSort * @功能：快速排序 * @作者：2019/3/12 * @修改者: */
        public void quickSort(int[] numbers, int low, int height) { 
            //递归的出口
            if (height <= low) { 
                return;
            }
    
            //三数取中
            int mid = (low + height) / 2;
            if (numbers[mid] > numbers[height]) { 
                swap(numbers, mid, height);
            }
            if (numbers[low] > numbers[height]) { 
                swap(numbers, low, height);
            }
    
            int base = numbers[low];
            int lo = low;
            int hi = height;
            while (lo < hi) { 
                //从右往左找比Base小的数
                while (lo < hi && numbers[hi] >= base) { 
                    hi--;
                }
                numbers[lo] = numbers[hi];
                //从左往右找比base大的数
                while (lo < hi && numbers[lo] <= base) { 
                    lo++;
                }
                numbers[hi] = numbers[lo];
            }
            //重合以后
            numbers[lo] = base;
    
            quickSort(numbers, low, lo);
            quickSort(numbers, lo + 1, height);
    
        }
    
        public void swap(int[] arr, int a, int b) { 
            int temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }

## 堆排序 ##

完整的堆排序要反复经过两个步骤：构造大根堆结构，堆排序输出。  
不画图了提供一个写的比较好的堆排序教程：[https://www.cnblogs.com/Java3y/p/8639937.html][https_www.cnblogs.com_Java3y_p_8639937.html]

public void heapSort(int a[], int n) { 
            //构造大根堆
            //完全二叉树获得最后非叶节点公式 数组长度/2-1
            int j;
            for (int i = n / 2 - 1; i >= 0; i--) { 
                buildHeap(a, i, n);
            }
    
            //排序
            for (int k = n - 1; k >= 0; k--) { 
                swap(a, 0, k);
                buildHeap(a, 0, k);
            }
        }
    
        public void buildHeap(int[] numbers, int i, int n) { 
    
            int j;
            //左子节点获取公式，当前父节点的两倍 + 1
            //判断是否有子叶节点，若左子叶不存在，那么右子叶也不可能存在
            while ((2 * i + 1) < n) { 
                j = 2 * i + 1;
                //判断右子叶是否存在，存在则选出左右子叶中较大的
                if ((j + 1) < n) { 
                    //j = numbers[j] > numbers[j + 1] ? j : j + 1;
                    if (numbers[j] < numbers[j + 1]) { 
                        j++;
                    }
                }
                //将左右子叶中较大的与父节点进行对比
                if (numbers[j] > numbers[i]) { 
                    swap(numbers, i, j);
                    //换位后可能会破坏大根堆
                    i = j;
                } else { 
                    break;
                }
            }
        }
    
        public void swap(int[] arr, int a, int b) { 
            int temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }

## 归并排序 ##

推荐一个学习归并排序的博客，[https://www.cnblogs.com/of-fanruice/p/7678801.html][https_www.cnblogs.com_of-fanruice_p_7678801.html]

public void mergeSort(int[] arr, int[] temp, int left, int right) { 
            //递归的出口，当左右相等时只有一个数字，一个数字默认看作有序的
            if (left == right) { 
                return;
            }
            int mid = (left + right) / 2;
            //递归分割
            mergeSort(arr, temp, left, mid);
            mergeSort(arr, temp, mid + 1, right);
            //合并
            merge(arr, temp, left, right, mid);
        }
    
        public void merge(int[] arr, int[] temp, int left, int right, int mid) { 
            int i, j, k;
    
            i = left;
            j = mid + 1;
            k = 0;
            //对比两个序列中的数字获得小的数放入新的数组中然后获取数的那组的下标++，因为是有序的所以从下到上可以保证按照顺序获取。
            while (i <= mid && j <= right) { 
                if (arr[i] < arr[j]) { 
                    temp[k++] = arr[i++];
                } else { 
                    temp[k++] = arr[j++];
                }
            }
            //当一侧的指针已经超出数组的长度则停止，那么另一侧剩下的数字都比它大，所以直接复制进数组
            //左侧剩下的移入数组
            while (i <= mid) { 
                temp[k++] = arr[i++];
            }
            //右侧剩下的移入数组
            while (j <= right) { 
                temp[k++] = arr[j++];
            }
            //将临时数组复制到arr，注意的是对应原数组的位置
            for (int i1 = 0; i1 < k; i1++) { 
                arr[left + i1] = temp[i1];
            }
        }

[https_blog.csdn.net_u012102104_article_details_79773907]: https://blog.csdn.net/u012102104/article/details/79773907
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70]: /images/20220309/de93f551bdda42d19fd6acafe401f3ca.png
[https_www.cnblogs.com_Java3y_p_8639937.html]: https://www.cnblogs.com/Java3y/p/8639937.html
[https_www.cnblogs.com_of-fanruice_p_7678801.html]: https://www.cnblogs.com/of-fanruice/p/7678801.html