# NC140.排序

# 题目描述

给定一个长度为n的数组，请你编写一个函数，返回该数组排序后的结果。

TIP

标签：排序

关联企业：字节跳动、阿里、度小满、百度

# 分析

基础的排序算法，时间复杂度都是O(n^2)级别的。这里限定时间复杂度，很明显要求使用快速排序算法来解决。

先来个基础的排序算法热热身：

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 将给定数组排序
 * @param arr int整型一维数组 待排序的数组
 * @return int整型一维数组
 */
function MySort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] > arr[j]) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
      }
    }
  }
  return arr;
}
module.exports = {
  MySort: MySort,
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

再来一版快速排序的实现

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 将给定数组排序
 * @param arr int整型一维数组 待排序的数组
 * @return int整型一维数组
 */
function MySort( arr ) {
  if(arr.length <= 1) {
    return arr
  } 
  let left = []
  let right = []
  let index = Math.floor((arr.length) / 2)
  let privot = arr.splice(index,1)[0]

  for (let i = 0; i < arr.length; i++) {
    if(arr[i] < privot) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return MySort(left).concat([privot],MySort(right))
}
module.exports = {
  MySort : MySort
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

下面是ts的解法

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 将给定数组排序
 * @param arr int整型一维数组 待排序的数组
 * @return int整型一维数组
 */
export function MySort(arr: number[]): number[] {
  // 我思考的快速排序需要使用递归的方式去解决，那么就需要递归的终止条件
  if (arr.length <= 1) {
    return arr;
  }

  // 需要两个数组，分别存放相对小的数字和相对大的数字
  let left = [];
  let right = [];
  // 需要声明一个索引，这个索引，初始化位置其实并没有想象的那么重要，我们一般习惯于将其设置为中间的数字
  // 数组的长度除以二 然后向下取整，这个索引，我们认为是数组的中间索引
  let index = Math.floor(arr.length / 2);
  // 将这个索引的位置的数字取出来
  // 数组的splice方法，会从索引位置开始截取指定数量的数组并且返回一个新的数组
  let privot = arr.splice(index, 1)[0];

  for (let i = 0; i < arr.length; i++) {
    // 每个元素都应该判断和privot的大小关系
    if (arr[i] < privot) {
      left.push(arr[i]);
    } else {
      // 大于或者等于的情况放在右边的数组
      right.push(arr[i]);
    }
  }
  // 指定递归调用
  return MySort(left).concat(privot, MySort(right));
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# 易错点：

我在写这道题目的时候，险些忘记递归的思想，因为需要递归。当数组中只有一个元素的时候直接返回当前数组就好了
如果保存快速排序的数组的长度，就会提交超时，确实不知道为什么会这样。这个还需要继续调试研究一下。

# 1027书写记录

首次提交的时候，在声明privot变量的时候，使用splice方法时候出现了失误，我写成了 splice(0.index) 实际上应该写成 splice(index,1)

# 20220916

let index = Math.floor((left + right) / 2); // 错的离谱
let privot = arr.splice(index)[0]; // 接收两个参数，我这里只写了一个参数

1
2