选择排序算法【重要】

目录

• 目录
• 算法复杂度
• 稳定性
• 代码演示：

选择排序法是一种不稳定的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。
最大趟数：n-1
每趟比较下标的最大值是最后一个元素：也就是j<=n-1

算法复杂度

空间复杂度：O（1）,因为用了一个临时变量来保存标记。
时间复杂度：
比较次数：n^2，因为2个for循环
交换次数：n-1，因为每趟只为了找一个下标，比较完一趟后，然后交换一次。
总时间：O(n^2)

稳定性

不稳定的算法

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。 举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法

代码演示：

function sortArray(arr) {
    for (let i = 0; i < arr.length-1;i++) {
        let pos = i;
        for(let j = i +1; j < arr.length;j++){
            if(arr[pos] > arr[j]){
                pos = j;
            }
        }
        let tmp = arr[i];
            arr[i] = arr[pos];
            arr[pos] = tmp;
    }
}

%23%23%23%20%E7%9B%AE%E5%BD%95%0A%5Btoc%5D%0A%20%20%0A%0A%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F%E6%B3%95%E6%98%AF%E4%B8%80%E7%A7%8D%E4%B8%8D%E7%A8%B3%E5%AE%9A%E7%9A%84%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E3%80%82%E5%AE%83%E7%9A%84%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E6%98%AF%E6%AF%8F%E4%B8%80%E6%AC%A1%E4%BB%8E%E5%BE%85%E6%8E%92%E5%BA%8F%E7%9A%84%E6%95%B0%E6%8D%AE%E5%85%83%E7%B4%A0%E4%B8%AD%E9%80%89%E5%87%BA%E6%9C%80%E5%B0%8F%EF%BC%88%E6%88%96%E6%9C%80%E5%A4%A7%EF%BC%89%E7%9A%84%E4%B8%80%E4%B8%AA%E5%85%83%E7%B4%A0%EF%BC%8C%E5%AD%98%E6%94%BE%E5%9C%A8%E5%BA%8F%E5%88%97%E7%9A%84%E8%B5%B7%E5%A7%8B%E4%BD%8D%E7%BD%AE%EF%BC%8C%E7%84%B6%E5%90%8E%EF%BC%8C%E5%86%8D%E4%BB%8E%E5%89%A9%E4%BD%99%E6%9C%AA%E6%8E%92%E5%BA%8F%E5%85%83%E7%B4%A0%E4%B8%AD%E7%BB%A7%E7%BB%AD%E5%AF%BB%E6%89%BE%E6%9C%80%E5%B0%8F%EF%BC%88%E5%A4%A7%EF%BC%89%E5%85%83%E7%B4%A0%EF%BC%8C%E7%84%B6%E5%90%8E%E6%94%BE%E5%88%B0%E5%B7%B2%E6%8E%92%E5%BA%8F%E5%BA%8F%E5%88%97%E7%9A%84%E6%9C%AB%E5%B0%BE%E3%80%82%E4%BB%A5%E6%AD%A4%E7%B1%BB%E6%8E%A8%EF%BC%8C%E7%9B%B4%E5%88%B0%E5%85%A8%E9%83%A8%E5%BE%85%E6%8E%92%E5%BA%8F%E7%9A%84%E6%95%B0%E6%8D%AE%E5%85%83%E7%B4%A0%E6%8E%92%E5%AE%8C%E3%80%82%0A%0A%E6%9C%80%E5%A4%A7%E8%B6%9F%E6%95%B0%EF%BC%9An-1%0A%E6%AF%8F%E8%B6%9F%E6%AF%94%E8%BE%83%E4%B8%8B%E6%A0%87%E7%9A%84%E6%9C%80%E5%A4%A7%E5%80%BC%E6%98%AF%E6%9C%80%E5%90%8E%E4%B8%80%E4%B8%AA%E5%85%83%E7%B4%A0%EF%BC%9A%E4%B9%9F%E5%B0%B1%E6%98%AFj%3C%3Dn-1%0A%0A!%5B1c7e20f306ddc02eb4e3a50fa7817ff4.gif%5D(evernotecid%3A%2F%2FD2915699-A379-4AAB-999E-4534E3EAFB1A%2Fappyinxiangcom%2F25807730%2FENResource%2Fp8)%0A%0A%23%23%23%20%E7%AE%97%E6%B3%95%E5%A4%8D%E6%9D%82%E5%BA%A6%0A%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%EF%BC%9AO%EF%BC%881%EF%BC%89%2C%E5%9B%A0%E4%B8%BA%E7%94%A8%E4%BA%86%E4%B8%80%E4%B8%AA%E4%B8%B4%E6%97%B6%E5%8F%98%E9%87%8F%E6%9D%A5%E4%BF%9D%E5%AD%98%E6%A0%87%E8%AE%B0%E3%80%82%0A%0A%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%EF%BC%9A%0A%E6%AF%94%E8%BE%83%E6%AC%A1%E6%95%B0%EF%BC%9An%5E2%EF%BC%8C%E5%9B%A0%E4%B8%BA2%E4%B8%AAfor%E5%BE%AA%E7%8E%AF%0A%E4%BA%A4%E6%8D%A2%E6%AC%A1%E6%95%B0%EF%BC%9An-1%EF%BC%8C%E5%9B%A0%E4%B8%BA%E6%AF%8F%E8%B6%9F%E5%8F%AA%E4%B8%BA%E4%BA%86%E6%89%BE%E4%B8%80%E4%B8%AA%E4%B8%8B%E6%A0%87%EF%BC%8C%E6%AF%94%E8%BE%83%E5%AE%8C%E4%B8%80%E8%B6%9F%E5%90%8E%EF%BC%8C%E7%84%B6%E5%90%8E%E4%BA%A4%E6%8D%A2%E4%B8%80%E6%AC%A1%E3%80%82%0A%E6%80%BB%E6%97%B6%E9%97%B4%EF%BC%9AO(n%5E2)%0A%0A%23%23%23%20%E7%A8%B3%E5%AE%9A%E6%80%A7%0A%0A%E4%B8%8D%E7%A8%B3%E5%AE%9A%E7%9A%84%E7%AE%97%E6%B3%95%0A%0A%3E%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F%E6%98%AF%E7%BB%99%E6%AF%8F%E4%B8%AA%E4%BD%8D%E7%BD%AE%E9%80%89%E6%8B%A9%E5%BD%93%E5%89%8D%E5%85%83%E7%B4%A0%E6%9C%80%E5%B0%8F%E7%9A%84%EF%BC%8C%E6%AF%94%E5%A6%82%E7%BB%99%E7%AC%AC%E4%B8%80%E4%B8%AA%E4%BD%8D%E7%BD%AE%E9%80%89%E6%8B%A9%E6%9C%80%E5%B0%8F%E7%9A%84%EF%BC%8C%E5%9C%A8%E5%89%A9%E4%BD%99%E5%85%83%E7%B4%A0%E9%87%8C%E9%9D%A2%E7%BB%99%E7%AC%AC%E4%BA%8C%E4%B8%AA%E5%85%83%E7%B4%A0%E9%80%89%E6%8B%A9%E7%AC%AC%E4%BA%8C%E5%B0%8F%E7%9A%84%EF%BC%8C%E4%BE%9D%E6%AC%A1%E7%B1%BB%E6%8E%A8%EF%BC%8C%E7%9B%B4%E5%88%B0%E7%AC%ACn-1%E4%B8%AA%E5%85%83%E7%B4%A0%EF%BC%8C%E7%AC%ACn%E4%B8%AA%E5%85%83%E7%B4%A0%E4%B8%8D%E7%94%A8%E9%80%89%E6%8B%A9%E4%BA%86%EF%BC%8C%E5%9B%A0%E4%B8%BA%E5%8F%AA%E5%89%A9%E4%B8%8B%E5%AE%83%E4%B8%80%E4%B8%AA%E6%9C%80%E5%A4%A7%E7%9A%84%E5%85%83%E7%B4%A0%E4%BA%86%E3%80%82%E9%82%A3%E4%B9%88%EF%BC%8C%E5%9C%A8%E4%B8%80%E8%B6%9F%E9%80%89%E6%8B%A9%EF%BC%8C%E5%A6%82%E6%9E%9C%E4%B8%80%E4%B8%AA%E5%85%83%E7%B4%A0%E6%AF%94%E5%BD%93%E5%89%8D%E5%85%83%E7%B4%A0%E5%B0%8F%EF%BC%8C%E8%80%8C%E8%AF%A5%E5%B0%8F%E7%9A%84%E5%85%83%E7%B4%A0%E5%8F%88%E5%87%BA%E7%8E%B0%E5%9C%A8%E4%B8%80%E4%B8%AA%E5%92%8C%E5%BD%93%E5%89%8D%E5%85%83%E7%B4%A0%E7%9B%B8%E7%AD%89%E7%9A%84%E5%85%83%E7%B4%A0%E5%90%8E%E9%9D%A2%EF%BC%8C%E9%82%A3%E4%B9%88%E4%BA%A4%E6%8D%A2%E5%90%8E%E7%A8%B3%E5%AE%9A%E6%80%A7%E5%B0%B1%E8%A2%AB%E7%A0%B4%E5%9D%8F%E4%BA%86%E3%80%82%0A%E4%B8%BE%E4%B8%AA%E4%BE%8B%E5%AD%90%EF%BC%8C%E5%BA%8F%E5%88%975%208%205%202%209%EF%BC%8C%E6%88%91%E4%BB%AC%E7%9F%A5%E9%81%93%E7%AC%AC%E4%B8%80%E9%81%8D%E9%80%89%E6%8B%A9%E7%AC%AC1%E4%B8%AA%E5%85%83%E7%B4%A05%E4%BC%9A%E5%92%8C2%E4%BA%A4%E6%8D%A2%EF%BC%8C%E9%82%A3%E4%B9%88%E5%8E%9F%E5%BA%8F%E5%88%97%E4%B8%AD%E4%B8%A4%E4%B8%AA5%E7%9A%84%E7%9B%B8%E5%AF%B9%E5%89%8D%E5%90%8E%E9%A1%BA%E5%BA%8F%E5%B0%B1%E8%A2%AB%E7%A0%B4%E5%9D%8F%E4%BA%86%EF%BC%8C%E6%89%80%E4%BB%A5%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F%E6%98%AF%E4%B8%80%E4%B8%AA%E4%B8%8D%E7%A8%B3%E5%AE%9A%E7%9A%84%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%0A%0A%23%23%23%20%E4%BB%A3%E7%A0%81%E6%BC%94%E7%A4%BA%EF%BC%9A%0A%0A%20%20%0A%0A%0A%60%60%60%0Afunction%20sortArray(arr)%20%7B%0A%09for%20(let%20i%20%3D%200%3B%20i%20%3C%20arr.length-1%3Bi%2B%2B)%20%7B%0A%09%09let%20pos%20%3D%20i%3B%0A%09%09for(let%20j%20%3D%20i%20%2B1%3B%20j%20%3C%20arr.length%3Bj%2B%2B)%7B%0A%09%09%09if(arr%5Bpos%5D%20%3E%20arr%5Bj%5D)%7B%0A%09%09%09%09pos%20%3D%20j%3B%0A%09%09%09%7D%0A%09%09%7D%0A%09%09let%20tmp%20%3D%20arr%5Bi%5D%3B%0A%09%09%09arr%5Bi%5D%20%3D%20arr%5Bpos%5D%3B%0A%09%09%09arr%5Bpos%5D%20%3D%20tmp%3B%0A%09%7D%0A%7D%0A%60%60%60