【21天学习挑战赛】算法——快速排序

活动地址：CSDN21天学习挑战赛

快速排序思想

快速排序最重要的思想是分而治之。
在一堆需要排序的数字中，取出任意一个数字m，将所有小于m的数字放在这个数字左边，所有大于m的数字放在右边。然后在分别对左边和右边的数字继续以上的操作，最后就可以得到有序的序列。

枢纽的选择

枢纽是把数据分为两部分的数字。
第一一种方案是直接选择第一个元素作为枢纽，但第一个作为枢纽在某些情况下，效率并不是特别高。
第二种方案是使用随机数，但是随机数本身就是一个耗性能的操作
第三种方案是取头、中、尾的中位数

function swap(arr, left,right){
	let temp = arr[right];
	arr[right] = arr[left];
	arr[left] = temp;
}
function media(arr, left, right){
	// 取出中间的位置
	let center = Math.floor((left + right) / 2);
	//判断大小并进行交换
	if(arr[left] > arr[center]){
		swap(arr, left, center);
	} 
	if(arr[center] > arr[right]){
		swap(arr, center， right);
	}
	if(arr[left] > arr[right]){
		swap(arr, left, right);
	}
	// 经过前面一系列的判断后center指向的元素一定比最后一个小，在后面的判断中最后一个元素不会再变动。
	swap(center, right-1);
	return arr[right - 1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

快速排序代码

function quickSort(arr, ){
  quick(0, arr.length - 1);
}

function quick(arr, left,right){
  if(left >= right){
    return ;
  }
  // 获取枢纽
  let privot = media(arr, left, right);
  let i = left;
  let j = right;
  while(true){
    while (arr[++i] < privot){
      
    }
    while(arr[--j] > privot){
      if(i < j){
        swap(i, j);
      } else {
        break;
      }
    }
  }
  // 把枢纽放置在正确的位置, 即i的位置
  swap(i, right - 1);

  // 分而治之
  quick(left, i - 1);
  quick(i+1, 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

下面使用的是把第一个元素作为枢纽的方式。
在列表中选择一个元素作为基准值，将小于基准值的元素排在数组的左边，将大于基准值的元素排在数组的左边。再分别对左边和右边的数据进行分割。

function quickSort(arr){
	if (arr.length === 0 ) return [];
	let left = [];
	let right = [];
	let privot = arr[0];
	for(let i = 1; i< arr.length; i++){
		if(arr[i] < privot){
			left.push(arr[i]);	
		} else {
			right.push(arr[i]);
		}
	}
	return quickSort(left).concat(privot,quickSort(right));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

快速排序复杂度分析

时间复杂度

在最坏情况下，即每次选择的枢纽是最左边或最后边的数据。这种情况下效率等同于冒泡排序。
平均效率是O(n*logn)

空间复杂度

快速排序使用变量存储元素的索引，属于常数级别的复杂度即O(1)