快速排序

 1 **
 2  * 快速排序
 3  */
 4 
 5 var temp;
 6 Object.prototype.swap = function (arr, index_1, index_2) {
 7     var tmp = arr[index_1];
 8     arr[index_1] = arr[index_2];
 9     arr[index_2] = tmp;
10 }
11 
12 function partition(arr, start, end) {
13     temp = arr[start];
14     while (start < end) {
15         while (start < end && arr[end] >= temp)--end;
16         swap(arr, start, end);
17         while (start < end && arr[start] <= temp)++start;
18         swap(arr, end, start);
19     }
20     return start;
21 }
22 
23 function quickSort(arr, start, end) {
24     if (start < end) {
25         var num = partition(arr, start, end);
26         quickSort(arr, num + 1, end);
27         quickSort(arr, start, num - 1);
28     } else {
29         console.log(arr);
30         return;
31     }
32 }
33 
34 var arr = [2, 1, 3, 2];
35 
36 quickSort(arr, 0, 3);
37 
38 /**
39  * 找出数组第k小的值
40  * 在快速排序的基础上引用二分法的概念，当找到第k位时，说明是最小
41  */
42 var temp;
43 Object.prototype.swap = function (arr, index_1, index_2) {
44     var tmp = arr[index_1];
45     arr[index_1] = arr[index_2];
46     arr[index_2] = tmp;
47 }
48 
49 function partition(arr, start, end) {
50     temp = arr[start];
51     while (start < end) {
52         while (start < end && arr[end] >= temp)--end;
53         swap(arr, start, end);
54         while (start < end && arr[start] <= temp)++start;
55         swap(arr, end, start);
56     }
57     return start;
58 }
59 
60 function findK(arr, key) {
61     // if (start == (key - 1)) {
62     //     console.log(‘第k小的为‘ + arr[key-1]);
63     //     return;
64     // }
65     var start = 0;
66     var end = arr.length - 1;
67     var num = partition(arr, start, end);
68 
69     while (start < end) {
70         if (num == key - 1) {
71             console.log(arr[num]);
72             return;
73         }
74         else if (num < key) {
75             start = num + 1;
76             num = partition(arr, start, end);
77         }
78         else {
79             end = num - 1;
80             num = partition(arr, start, end);
81         }
82     }
83 
84     console.log("not found!");
85 }
86 
87 var arr = [10, 25, 38, 44];
88 findK(arr, 6);