算法疑难(js实现)---1、快速排序

一、总结

一句话总结：

快排就是将数列按照基准数分成左（左区间都比基准数小）右（右区间都比基准数大）两个区间，对左右区间递归快排，直到区间只有一个数，这样区间就全部有序了，然后将全部有序的区间合并起来就得到排序好的结果

 1 function quickSort(arr) {
 2     //1、找基准数，并且将比基准数小的全部放到左边（左数组），
 3     // 大于等于基准数的全部放到右边（右数组）
 4     let base_num=arr[0];//基准数
 5     let left_arr=[];//左数组
 6     let right_arr=[];//右数组
 7     for (let i=1;i<arr.length;i++){
 8         //比基准数小的都放在左数组，否则放在右数组
 9         if(arr[i]<base_num){
10             left_arr.push(arr[i]);
11         }else{
12             right_arr.push(arr[i]);
13         }
14     }
15 
16     //2、对左右数组分别进行快排，返回排序好的左右数组
17     // （条件：就是数组中的元素要大于等于2个）
18     if(left_arr.length>=2) left_arr=quickSort(left_arr);
19     if(right_arr.length>=2) right_arr=quickSort(right_arr);
20     //快排之后的left_arr和right_arr 都是有序
21 
22     //3、合并排序好之后的左数组、基准数、排序好的右数组，并且返回
23     return left_arr.concat(base_num,right_arr);
24 }

1、快排的思路？

1、拆分区间：先从数列中取出一个数作为基准数，将比这个数小的全放到它的左边，大于或等于它的数全放到它的右边

2、递归：再对左右区间重复第1步，直到各区间只有一个数，区间只有一个数，这样区间就有序了

3、合并区间：将有序的区间合并起来，这样整个数列就有序了

二、快速排序

博客对应课程的视频位置：1、快速排序
https://www.fanrenyi.com/video/20/173

 1 <!DOCTYPE html>
 2 <html lang="en">
 3 <head>
 4     <meta charset="UTF-8">
 5     <title>快速排序</title>
 6 </head>
 7 <body>
 8 <!--
 9 快速排序的思路：
10 1、先从数列中取出一个数作为基准数
11 2、将比这个数小的全放到它的左边，大于或等于它的数全放到它的右边
12 3、再对左右区间重复第二步，直到各区间只有一个数
13 4、将有序的区间合并起来，这样整个数列就有序了
14 
15 let arr=[31,23,34,2,13,234];
16 
17 第一步：比如取第一个数为基准数，比31小的都放31左边，比31大的都放到31的右边
18 
19 23,2,13,  31  ,34,234
20 
21 第二步：对31 左右两边的数组都做同样的操作：选基准数，比基准数小的放左边，比基准数大的放右边
22 左边：[23,2,13]：选23为基准：2,13,  23
23 
24 右边：[34,234]：选34为基准：34,  234
25 2,13,23,31,34,234
26 
27 -->
28 <script>
29     let arr=[31,23,34,2,13,234,31,43,343,65,23,43,13,2];
30 
31     function quickSort(arr) {
32         //1、找基准数，并且将比基准数小的全部放到左边（左数组），
33         // 大于等于基准数的全部放到右边（右数组）
34         let base_num=arr[0];//基准数
35         let left_arr=[];//左数组
36         let right_arr=[];//右数组
37         for (let i=1;i<arr.length;i++){
38             //比基准数小的都放在左数组，否则放在右数组
39             if(arr[i]<base_num){
40                 left_arr.push(arr[i]);
41             }else{
42                 right_arr.push(arr[i]);
43             }
44         }
45 
46 
47         //2、对左右数组分别进行快排，返回排序好的左右数组
48         // （条件：就是数组中的元素要大于等于2个）
49         if(left_arr.length>=2) left_arr=quickSort(left_arr);
50         if(right_arr.length>=2) right_arr=quickSort(right_arr);
51         //快排之后的left_arr和right_arr 都是有序
52 
53 
54         //3、合并排序好之后的左数组、基准数、排序好的右数组，并且返回
55         return left_arr.concat(base_num,right_arr);
56 
57     }
58     let ans=quickSort(arr);
59     console.log(ans);
60 </script>
61 </body>
62 </html>