选择排序

1. 基本介绍选择式排序（select sorting）也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。 2. 选择排序思想基本思想是：第一次从 arr[0]~arr[n-1]中选取最小值，与 arr[0]交换，第二次从 arr[1]~arr[n-1]中选取最小值，与 arr[1]交换，第三次从 arr[2]~arr[n-1]中选取最小值，与 arr[2]交换，…，第 i 次从 arr[i-1]~arr[n-1]中选取最小值，与 arr[i-1]交换，…, 第 n-1 次从 arr[n-2]~arr[n-1]中选取最小值，与 arr[n-2]交换，总共通过 n-1 次，得到一个按排序码从小到大排列的有序序列。 3. 选择排序理解![选择排序动图]() 3.1 选择排序图解 1.选择排序一共有数组大小-1 次排序2.每一次排序，又是一个循环，循环规则如下 2.1 先假定当前这个数是最小数 2.2 然后和后面的每个数进行比较，如果发现有比当前数更小的数，就重新确定最小数，并得到下标 2.3 当遍历到数组的最后时，就得到本轮最小数和小标 2.4 交换代码，再继续 4. 选择排序代码/** * @author: Coder编程 * @create: 2019-6-20 22:06 * @description: 选择排序 **/public class SelectionSort { /** * 选择排序 * @param arr 待排序数组 */ public void selectionSort(Integer[] arr) { // 需要遍历获得最小值的次数 // 要注意一点，当要排序 N 个数，已经经过 N-1 次遍历后，已经是有序数列 for (int i = 0; i < arr.length - 1; i++) { int minindex = i; // 用来保存最小值得索引 int min = arr[i]; // 用来保存最小值 for (int j = i + 1; j < arr.length; j++) { if (min > arr[j]) {// 说明假定的最小值，并不是最小 min = arr[j]; // 重置 min minindex = j; // 重置 minIndex } } // 如果假定最小值的索引发生了改变，则进行交换 if(minindex != i){ arr[minindex] = arr[i]; //此时minindex为j，因此i与j交换 arr[i] = min; //最小值给下标i } System.out.format("\n第 %d 趟:\t", i + 1); Arrays.asList(arr).stream().forEach(x -> System.out.print(x + " ")); } } public static void main(String[] args) { //初始数组 Integer arrays[] = {2,9,7,5,3}; // 调用选择排序方法 SelectionSort selection = new SelectionSort(); System.out.print("欢迎个人公众号Coder编程：选择排序前：\t"); Arrays.asList(arrays).stream().forEach(x -> System.out.print(x + " ")); selection.selectionSort(arrays); System.out.print("\n欢迎个人公众号Coder编程：选择排序后:\t"); Arrays.asList(arrays).stream().forEach(x -> System.out.print(x + " ")); } }打印结果 ...

导语这篇说下选择排序。选择排序选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对 n 个元素的表进行排序总共进行至多 n -1 次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种维基百科中的介绍。前两篇介绍的冒泡排序、快速排序都属于完全依靠交换去移动元素的排序方法。动图演示实例<?php$arr = [33, 24, 8, 21, 2, 23, 3, 32, 16];function selectSort($arr){ $count = count($arr); if ($count < 2) { return $arr; } for ($i = 0; $i < $count - 1; $i++) { // 当前值的位置 $key = $i; for ($k = $i + 1; $k < $count; $k++) { // 相邻值进行比较，条件成立替换当前值 // 倒序 $arr[$key] < $arr[$k] if ($arr[$key] > $arr[$k]) { $key = $k; } } if ($key != $i) { // 交换位置 $temp = $arr[$key]; $arr[$key] = $arr[$i]; $arr[$i] = $temp; } } return $arr;}print_r(selectSort($arr));// Array ( [0] => 2 [1] => 3 [2] => 8 [3] => 16 [4] => 21 [5] => 23 [6] => 24 [7] => 32 [8] => 33 ) 参考资料：选择排序、PHP 选择排序。 ...

基本排序算法在计算机科学中，一个排序算法是一种能将一串数据依照特定的排列方式进行排列的一种算法。这里简单的介绍三种最基本的排序，分别是：冒泡排序、选择排序以及插入排序排序的过程中，经常要用到交换元素位置，故抽离为公共函数 swap。// 交换位置export function swap(arr, index1, index2) { var temp = arr[index1]; arr[index1] = arr[index2]; arr[index2] = temp;}冒泡排序冒泡排序是最简单的排序，一一对比相邻的两个数，顺序不对就交换过来，这样子，每一轮最大的值总会慢慢的被交换到最右侧。所以才会叫冒泡排序描述假设数组长度为 n比较相邻的两个数，如果第 1 个大于第 2 个，就交换位置重复第 1 步，一轮下来最大值被交换到第 n 个位置，也就是最右侧开启新一轮，重复 12 步，最大值会被冒泡到第 n-1 个位置重复上述步骤，直到所有都排序好例子：对 3, 1, 5, 2, 4 进行排序1,3,5,2,4 3 > 1 ,交换位置1,3,5,2,4 3 < 5 ,不变1,3,2,5,4 5 > 2 ,交换位置1,3,2,4,5 5 > 4 ,交换位置,第一轮结束1,3,2,4,5 1 < 3 ,不变1,2,3,4,5 3 > 2 ,交换位置1,2,3,4,5 …依次对比1,2,3,4,5 …1,2,3,4,5 … 结束代码实现// 冒泡排序export function bubbleSort(array) { for (let i = array.length - 1; i >= 1; i–) { let hasSwap = false; for (let j = 0; j <= i; j++) { if (array[j] > array[j + 1]) { swap(array, j, j + 1); hasSwap = true; } } if (!hasSwap) { // 这里用于优化，如果某一轮之后，没有进行任何交换，说明已经排序完成了，所以退出循环 break; } }}效果演示https://global.chen4342024.co…注意打开开发者工具，切换到移动端模式小结冒泡算法是比较慢的排序之一，也是最容易实现的算法之一。复杂度稳定性：稳定时间复杂度： 平均 O(n^2) 、 最坏 O(n^2) 、最好 O(n)额外空间复杂度 O(1)选择排序选择排序是指每一轮从数组中取出最小值，然后跟第一个元素交换位置。然后再找出第二个最小值，跟第二个元素交换位置，。。。以此类推。直到倒数第二个位置例子对 3, 1, 5, 2, 4 进行排序// 这里只展示每一轮的结果3 1 5 2 4 //开始1 3 5 2 4 //第 1 轮1 2 5 3 4 //第 2 轮1 2 3 5 4 //第 3 轮1 2 3 4 5 //第 4 轮代码实现// 选择排序从开头开始，找出最小的值，放在第一个位置// 有点类似打扑克拍的时候，抽取每一张最小的放在最左边export function selectSort(array) { for (let i = 0; i < array.length - 1; i++) { let minIndex = i; let min = array[i]; for (let j = i + 1; j < array.length; j++) { if (array[j] < min) { min = array[j]; minIndex = j; } } swap(array, i, minIndex); }}效果演示https://global.chen4342024.co…注意打开开发者工具，切换到移动端模式复杂度稳定性：不稳定时间复杂度： O(n^2)额外空间复杂度 O(1)插入排序插入排序的思想是，依次从数组中未排序的部分，取出数据，然后插入到已排序的部分。直到清空未排序的部分描述假设数组长度为 n , 从第 2 项开始从第一个元素开始，该元素可以认为已经被排序；取出下一个元素，在已经排序的元素序列中从后向前扫描；如果该元素大于新元素，将该元素移到下一位置；重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；将新元素插入到该位置后；重复步骤 25。代码实现export function insertSort(array) { for (let i = 0; i < array.length; i++) { let temp = array[i]; let j = i; while (j > 0 && array[j - 1] > temp) { // 将所有大于temp的往右移 array[j] = array[j - 1]; j–; } array[j] = temp; }}效果演示https://global.chen4342024.co…注意打开开发者工具，切换到移动端模式复杂度稳定性：稳定时间复杂度：平均 O(n^2) 、 最坏 O(n^2) 、最好 O(n)额外空间复杂度 O(1)效果演示（汇总）https://global.chen4342024.co…注意打开开发者工具，切换到移动端模式总结这三种最基本的排序算法的复杂度非常相似，从理论上来说，它们的执行效率也应该差不多。在实际使用中，如果需要排序的数据比较多，是不推荐使用这 3 种排序的。毕竟他们的效率都不太理想在实际应用中，应该选择高级排序算法： 快速排序 …在随机生成数据测试的时候，发现很多时候，插入排序要快于冒泡排序以及选择排序。大概是冒泡/选择排序的快 1 倍这是因为 插入排序需要比较的次数是 1+2+3+..+n = n * (n-1) /2,这是最坏的情况，大部分时候并不需要全部比较，所以平均下来只需要 n*(n-1)/4而冒泡/选择排序都需要n * (n-1)/2,所以平均下来，插入排序大概是冒泡/选择排序的快 1 倍 ...