- 排序算法
- 交换算法
- 冒泡排序 - 交换算法 适合本身有序
- 算法分析
- 快速排序 - 交换算法 不适合本身有序
- 基本快排
- 优化:随机基准值的快排
- 算法分析
- 归并排序 与初始状态无关
- 算法分析
基本思想：两两比较，如果发生逆序则交换，直到所有记录都排好序位置
冒泡排序 - 交换算法 适合本身有序基于简单交换思想
基本思想:每趟不断将记录两两比较，并按"前小后大"规则交换。
每一躺确定一个最大的元素，所以n个元素需要n-1躺。
每一趟比较的次数 = n - 趟数。
如果某一趟比较时不出现记录交换，说明已经排好序了，可以提前结束了
优点
每趟结束时，不仅能让最大值找到位置，还能同时部分理顺其他元素。
function bubble(nums){
let n = nums.length;
for(let i=1;i //趟数
let flag = false;//false表示没有发生交换，true表示发生了交换,每一趟开始先置false
for(let j=0;j//每一趟比较的次数，因为选择nums的元素，所以让j从0开始
if(nums[j]>nums[j+1]){//发生逆序则交换
[nums[j],nums[j+1]]=[nums[j+1],nums[j]];
flag = true;
}
}
//一趟结束了
if(!flag) return nums; //如果某一趟没有元素交换，说明已经排好序了。
}
return nums;
}
算法分析
最好情况(正序)
比较次数：n-1
移动次数：0
最坏情况(逆序)
比较次数：1+2+…n-1
移动次数：3（比较次数）
最好时间复杂度：O(n)
最坏时间复杂度:O(n^2)
平均时间复杂度:O(n^2)
适合本身就有序的(正序）
快速排序 - 交换算法 不适合本身有序 基本快排思路
- 选择数组中一个元素(如第一个)为基准值pivotkey
- 开始寻找基准值最终的位置，比基准值小的放前面，比基准值大的放后面。最终就是基准值的位置，并且基准值将数组分为左右两个子表。（小 中 大）
- 左表和右表分别再执行1，2步。
- 直到每一个子表只剩下一个元素。
通过一趟排序，将排序的数组分隔成了两个部分，基准元素也找到最终的位置。
一个n个元素，那么就需要n-1趟。
采用递归的思想实现
1.递归的参数、返回值和停止递归的条件
一般采用左右边界的方法来对数组进行区间划分。
所以我们需要知道数组、左右边界。
我们通过在数组中交换元素进行排序，所以修改了数组本身的值，不需要返回值。
递归的终止条件是子表只有一个元素时，停止。
function qSort(nums,left,right){
//递归终止条件 为什么不是left=right，考虑基准值在边界的情况，那么下一次的left就会小于right
if(left>=right) return;
}
2.本层递归逻辑
寻找基准值的位置，根据基准值分为左右两个部分，左右那部分继续排序
function qSort(nums,left,right){
if(left
let index = partiton(nums,left,right);//寻找基准值的位置
qSort(nums,left,index-1);//左表排序
qSort(nums,index+1,right);//右表排序
}
}
function partiton(nums,left,right){
let pivotkey = nums[left]; //假设数组的第一个元素为基准点
while(left
//右边的指针先行，如果找到比基准点小的就可以去覆盖左边指针位置的值，而左边指针位置的值就是我们的基准点，已经被存起来了
while(left=pivotkey)right--;
nums[left]=nums[right];
while(left
优化:随机基准值的快排
基本快排的问题:不适合本身有序的数组，如果本身就有序就会退化成冒泡排序
通过随机选取基准值，可以降低初始顺序对快速排序效率的影响。
1.随机选取一个下标
1.1 范围在[left,right]之间，需要生成[left,right]之间的随机整数
2.该下标的值与第一个元素进行交换，就可以开始寻找基准值的位置了。
需要生成[left,right]之间的随机整数
Math.random() 随机 返回[0,1)随机数
Math.random()*(right-left+1) //[0,5)的随机数
Math.floor(Math.random()*(right-left+1)) //[0,5)的随机整数
left+Math.floor(Math.random()*(right-left+1)) //[2,7)的随机整数
随机基准值选取
let randomIndex = left+Math.floor(Math.random()*(right-left+1)) ;
[nums[randomIndex],nums[left]] = [nums[left],nums[randomIndex]];
let pivotkey = nums[left];
完整代码
function sortArray(nums: number[]): number[] {
let len = nums.length;
if(len==1)return nums;
qSort(nums,0,len-1);
return nums;
};
function qSort(nums,left,right){
if(left
let index = partiton(nums,left,right);//寻找基准值的位置
qSort(nums,left,index-1);//左表排序
qSort(nums,index+1,right);//右表排序
}
}
function partiton(nums,left,right){
let randomIndex = left+Math.floor((Math.random()*(right-left+1))) ;
[nums[randomIndex],nums[left]] = [nums[left],nums[randomIndex]];
let pivotkey = nums[left];
while(left
while(left=pivotkey)right--;
nums[left]=nums[right];
while(left
算法分析
- 时间复杂度 O（nlogn）
- QSort()递归的深度使logn:O(logn)
- partiton()：O(n)
- 空间复杂度 O（logn）
快速排序不适合对原本有序或基本有序的记录序列进行排序
划分元素的选取是影响时间性能的关键。
归并排序 与初始状态无关
当我们需要排序一个数组时，先将数组分成一半，想办法把左边的数组给排序，右边的数组给排序，之后再将它们归并起来。那现在对数组的排序就变成了对左边数组的排序和右边数组的排序。
当然了当我们对左边的数组和右边的素组进行排序的时候，再分别将左边的数组和右边的数组分成一半，然后对每一个部分归并。
什么时候停止递归，只有一个元素时已经有序了，就不用再排序了，直接归并就好了。
这个思路不就是递归的思路吗！归并的过程就是在递归。
递归三部曲
递归的参数和返回值
直接对原数组nums进行修改
参数需要原数组和两个划分区间的指针left、right
function merge (let nums,let left,let right){
}
递归的终止条件
只有一个元素时，自然就是有序的,不需要在进行划分了
if(left==right) return;
本层递归逻辑
本层递归需要把有序的两个部分合并成有序的一个部分。
function merge (nums,left,right){
if(left==right) return;
let mid = (left+right)>>1; //除以2的操作
merge(nums,left,mid); //左边的有序数组
merge(nums,mid+1,right);//右边的有序数组
//优化：如果此时已经有序了，就不用在进行有序合并了
if(nums[mid]<=nums[mid+1])return;
//对左边和右边数组进行排序合
mergeSort(nums,left,mid,right);
return nums;
}
//两个数组进行排序
function mergeSort(nums,left,mid,right){
let l =left;
let r = mid+1;
let k = 0;
let arr = new Array(right-left+1); //记录排好序的结果
while(l<=mid && r<=right){
if(nums[l]<=nums[r]) arr[k++] = nums[l++];
else arr[k++] = nums[r++];
}
while(l<=mid){
arr[k++] = nums[l++];
}
while(r<=right){
arr[k++] = nums[r++];
}
for(let i=0;i //新数组覆盖老数组
nums[left+i] = arr[i];
}
}
算法分析
- 时间复杂度：O(NlogN)，这里 N 是数组的长度；
- 空间复杂度：O(N)，辅助数组与输入数组规模相当
