基本的排序算法
算法的学习核心是：思路，知道思路，清楚思路，明白思路的思考过程，写代码就会很轻松
快速排序 （递归的方法）
快速排序就是大学学的折半查找算法，或者说是二分查找；时间复杂度：每次把搜索区减少一半，最坏的时间复杂度：
O(n*n)，最优的时间复杂度：O(n*logn)；n表示集合中元素的个数；空间复杂度：O(1)
-
对于一个给定的数组
var ary，思路- 首先取得数组中间位置上面的数，使其成为一个等待被比较的数组
left；
> 这个过程使用到数组的`ary.splice(parseInt(arr.length/2),1)`这个方法返回的是被删除的数组，要取得这个数组里面的数，需要这样：`ary.splice(parseInt(arr.length/2),1)[0]`，此时原来的`ary`中已经没有了中间的那个数组，变成了一个新的数组。- 创建两个空的数组，分别来保存比较的大值和小值
``` var left=[]; //存储与中间值比较的小值 var right=[]; //存储与中间值比较的大值 ```- 分别遍历数组中的每一项，与中间值进行比较
``` for(var i=0;i<arr.length;i++){ if(arr[i]>num){ right.push(arr[i]); }else{ left.push(arr[i]); } } ```- 返回排好顺序的数组，使用数组的拼接方法，把
left和right排好序的拼接起来concat()，由于left和right也是数组，它们里面的数也需要进行排序，此时使用递归
``` return quickSort(left).concat(num,quickSort(right)); ```- 最后要设置停止拆分的条件
``` if(arr.length<=1){ return arr;} ``` - 首先取得数组中间位置上面的数，使其成为一个等待被比较的数组
完整代码：
//封装成为一个比较函数,传入比较的数组
function quickSort(arr){
//第五步
if(arr.length<=1){
return arr;
}
//第一步
var num=arr.splice(parseInt(arr.length/2),1);
//第二步
var left=[];
var right=[];
//第三步
for(var i=0;i<arr.length;i++){
if(arr[i]<num){
left.push(arr[i]);
}else{
right.push(arr[i]);
}
}
//第四步
return quickSort(left).concat(num,quickSort(right));
}
插入排序 （不适合数据量比较大的排序）
思路：对于未排序的数组，在已经排好序的数组里面从后往前扫描。找到相对应的位置插入；最好的算法复杂度：
O(n)；最坏的算法复杂度：O(n*n)；空间复杂度：O(n)
- 首先创建一个数组
left，从要排序的数组里面取得一个数放入其中，作为我们比较的对象；此时的原数组里面不包括刚才我们所取得的那个数，变成了一个新的数组，防止取得的这个数与自己相比较。这里也要使用数组的arr.splice(0,1)；
var left=arr.splice(0,1)//返回从位置0删除一个的数组 - 遍历原先那个去掉比较对象的新数组，分别与我们的比较对象
left进行比较，从后往前
for(var i=0;i<arr.length;i++){
for(var j=left.length-1;j>=0;){
//进行比较left和arr[i]
if(arr[i]<left[j]){
//说明arr[i]的值比left[j]值小，我们需要向前继续向前查找left数组 故
j--;
//判断是否到了left数组的头部,到了就把arr[i]插入到left数组的头部
if(j==-1){
left.unshift(arr[i]);//此时的left数组变成了一个新的数组
}
}else{
//说明arr[i]比left[j]大，其应该插入到left[j]的前面位置
left.splice(j+1,0,arr[i]);
break;//此时一轮比较完毕，跳出内循环，重新开始外循环
}
}
}
- 最后返回已经排好序的数组
完整代码：
function insertSort(arr){
var left=arr.splice(0,1);
for(var i=0;i<arr.length;i++){
for(var j=left.length-1;j>=0;){
if(arr[i]<left[j]){
j--;
if(j==-1){
left.unshift(arr[i]);
}
}else{
left.splice(j+1,0,arr[i]);
break;
}
}
}
return left;
}
冒泡排序
- 比较相邻的元素。如果第一个比第二个大，就交换其位置
- 对每一个相邻元素作相同的工作，这一步完成就得到了最大的数，重复操作
- 时间复杂度：
O(n*n)，空间复杂度：O(n)，最优时间复杂度：O(n)
- 外循环决定轮数，内循环决定比较次数，
- 最简单的一种方法实现：
function bubbleSort(arr){
var tmp;
for(var i=0;i<arr.length;i++){
for(var j=i+1;j<arr.length;j++){
if(arr[i]>arr[j]){
tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
}
}
return arr;
}
- 稍微简单的一种方法实现：
function bubbleSort(arr){
var tmp;
for(var i=0;i<arr.length;i++){
for(var j=0;j<arr.length-i;j++){
if(arr[j]>arr[j+1]){
tmp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=tmp;
}
}
}
return arr;
}
- 封装一下，带有布尔值的参数，从而控制是从大到小还是从小到大的排序：
//带有布尔值的，传入true or false 来控制从大到小还是从小到大 不传默认fasle
function bubbleSort(arr, flag)
{
for(var i = 0; i < arr.length; i++)
{
for(var j = i + 1; j < arr.length; j++)
{
if(flag)
{
if(arr[i] > arr[j]) {
var tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
} else {
if(arr[i] < arr[j]) {
var tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
}
}
return arr;
}
- 继续封装，使用三目运算符，精简代码：
function bubbleSort(arr, flag) {
var bu;
for(var i = 0; i < arr.length; i++) {
for(var j = i + 1; j < arr.length; j++) {
bu = flag ? (arr[i] > arr[j]) : (arr[i] < arr[j]);
change(bu);
}
}
//把arr[i] > arr[j] 或者 arr[i] < arr[j] 传入
function change(flag) {
if(flag) {
var tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
return arr;
}
网友评论