1.冒泡排序
原理:冒泡排序的过程就是将数组中相邻的两个元素进行比较,如果前面的元素比后面的元素要大交换位置,否则位置不变;举个栗子:有数组 arr = [3,5,4,2,1];
第一轮循环:3和5比较,3小于5两者位置不变,接下来5和4比较,5大于4,两者交换位置,接着5和2比较,5>2两者交换位置,继续5和1 比较 5>1两者交换位置,一轮后得到的数组是[3,4,2,1,5];把大的元素放到数组的最末尾,这种就像水泡样一层一层的像后移动,就是冒泡排序了;
代码实现:
// 记录循环次数 let count = 0 // 位置交换函数 const change = function (arr, n1, n2) { // 用es6的实现交换 [arr[n1], arr[n2]] = [arr[n2], arr[n1]] //let temp = arr[n1] //arr[n1] = arr[n2] //arr[n2] = temp } // 冒泡排序 const bubbleSort = function (soucre) { let len = soucre.length for (let i = 0;i < len="" -="" 1;="" i++)="" {="" for="" (let="" j="0;" j="">< len="" -="" 1="" -="" i;j++)="" {="" count="" ++="" if="" (soucre[j]=""> soucre[j+1]) { change(soucre, j, j+1) } } } return soucre } //验证 console.log(bubbleSort([3,6,2,4,9,1,8])) // [1,2,3,4,6,8,9] console.log(count) // 21
2.选择排序
选择排序和冒泡排序类似也是依次对相邻的数进行两两比较。不同之处在于,他不是每次两两相邻比较后交换位置,他是先找出最大(最小)将它放到正确的位置,然后再寻找次最大(最小)放在正确的位置;
举个栗子:有数组 arr = [3,5,4,2,1];
先假设第一个元素是最小值,并定义一个minidx=0变量记录最小(最大)值的位置,for循环和其他元素进行比较,3和5进行比较,5>3此时不做处理,4也是一样处理,当3和2比较时,3>2,此时将minidx赋值为2的位置,接下来用arr[minidx]和剩余的元素比较遇到比他小的就用minidx记录小值的位置;最后将最小的位置值和初始给的值位置进行互换(当然是初始的值和一轮循环下来的minidx位置不一样才互换);所以一轮循环下来结果是arr = [1,5,4,2,3]
代码实现:
// 记录循环次数let count = 0// 选择排序 const selectSort = function (soucre) { let len = soucre.length let minidx; for (let i = 0; i < len;="" i="" ++)="" {="" minidx="i" for="" (let="" j="i" +="" 1;="" j="">< len;="" j++)="" {="" count="" ++="" if="" (soucre[minidx]=""> soucre[j]) { minidx = j } } if (minidx !== i) { change(soucre,i,minidx) } } return soucre } console.log(selectSort([3,6,2,4,9,1,8,23,45,16,14])) // [1, 2, 3, 4, 6, 8, 9, 14, 16, 23, 45] console.log(count) // 55
3.插入排序
原理:将数组分为已排序和未排序,将第一个元素看作是已排序的元素,而其他是未排序的,从未排序的里面取出一元素和已排序元素进行比较,并插入到正确位置,这样已排序部分增加一个元素,而未排序的部分减少一个元素。直到排序完成
举个栗子:有数组 arr = [1,5,4,2,3],第一次假设元素1 是已排序部分,5,4,2,3为未排序,取出元素5加入已排序部分,5>1,已排序部分为1,5;而未排序部分为4,2,3;如此往复完成排序;
代码实现:
const insertSort = function (source) { let len = source.length let value let j let i for (i = 0; i < len;="" i++)="" {="" value="source[i]" 已排序部分进行元素的右移一位,并把目标值value插入到对应的位置="" for="" (j="i" -1="" ;j=""> -1 && source[j] > value; j--) { source[j+1] = source[j] } source[j+1] = value } return source } console.log(insertSort([3,6,2,4,9,1,8])) // [1,2,3,4,6,8,9]
4.归并排序
原理: 将两个已经排序的数组合并,要比从头开始排序所有元素来得快。因此,可以将数组拆开,分成n个只有一个元素的数组,然后不断地两两合并,直到全部排序完成
代码实现:
const mergeSort = function mergeSort(source) { let len = source.length if (len < 2)="" {="" return="" source="" }="" let="" mid="Math.floor(len/2)" let="" left="source.slice(0,mid)" let="" right="source.slice(mid)" return="" merge(mergesort(left),="" mergesort(right))="" }="" function="" merge(left,="" right)="" {="" let="" result="[]" while="" (left.length="" &&="" right.length)="" {="" if="" (left[0]=""><= right[0])="" {="" result.push(left.shift())="" }="" else="" {="" result.push(right.shift())="" }="" }="" while="" (left.length){="" result.push(left.shift())="" }="" while="" (right.length){="" result.push(right.shift())="" }="" return="" result="" }="" console.log(mergesort([4,8,1,3,5,9,6]))="">=>
5.快速排序
原理:快速排序是目前公认的速度快和高效的排序方式,时间复杂度O(nlogn)是比较理想的状态,他的实现过程是,先在数组找到一个基点,把大于这个基点的值放到右侧,小于基点的值放到左侧,再将右侧的和左侧的也按照这种方式再次分配,直到完成排序
举个栗子:有一个数组 arr = [1,5,4,2,3];假设我们找数组的中间点作为基点也就是4,那一轮循环后结果就是[1,2,3,4,5] ->_->怎么这么巧,一轮就OK,果然是快速排序,就是快 哈哈,当然程序不会这么做,他是严谨的,他还会去拆分[1,2,3]只是这个实际上已经是排好了的;
代码实现:粗糙一点的
const quire = function quire(source) { if(source.length < 2)="" return="" source="" let="" left="[]" let="" right="[]" let="" len="source.length" let="" key="source[Math.floor(len/2" -1)]="" for="" (let="" i="">< key)="" {="" left.push(source[i])="" }="" else="" if="" (source[i]=""> key){ right.push(source[i]) } } return [].concat(quire(left),key,quire(right)) }
上面这种方法缺点就是空间浪费,他会创建很多个left 和 right 这样的数组,造成空间的浪费,当数据量一大的话还是很恐怖的,所以我们要改进的就是,不新建中间数组,而是直接修改位移目标数组;
改进原理: 选取一个基点,从数组的两头两个指针分别向基点位移,位移的原则是,基点的左边的元素如果小于基点,那就像基点位置靠拢一位,i++,如果大于基点就原地不动,基点右边的元素反过来,如果大于基点就像基点靠拢一位,j--;如果小于就原地不动;这时再比较两个原地不动的点,如果右边的不动点小于左边的值,就互换他们的位置;
代码实现:
// 位置交换 const change = function (arr, n1, n2) { // let temp = arr[n1] // arr[n1] = arr[n2] // arr[n2] = temp // 用es6的实现交换 [arr[n1], arr[n2]] = [arr[n2], arr[n1]] } const quiregai = function quiregai(source, start, end) { let pivot = source[Math.floor((start + end)/2)] let i = start // 左边指针初始位置 let j = end // 右边指针初始位置 while(i<=j) {="" while="" (source[i]="">=j)>< pivot)="" {="" i="" ++="" 左指针右移="" }="" while="" (source[j]=""> pivot) { j -- // 右指针左移 } if (i <= j){="" change(source,i,j)="" 交换两个位置的值="" i++="" j--="" }="" }="" return="" i="" 返回一轮循环后左指针的位置,为下一轮循环初始位置确定="" }="" const="" quiregaisort="function" quiregaisort(source,="" start,="" end)="" {="" if="" (source.length="">=>< 2)="" return="" source="" var="" start="start" ||="" 0="" var="" end="end" ||="" source.length="" -="" 1="" var="" nextstart="quiregai(source," start,="" end)//="" debugger="" if="" (start="">< nextstart="" -1)="" {="" quiregaisort(source,="" start,="" nextstart="" -1="" )="" 上个循环结束的左指针作为左边区块循环的右指针="" }="" if="" (nextstart="">< end)="" {="" quiregaisort(source,="" nextstart,="" end)="" 上个循环结束的左指针作为右边区块循环的左指针="" }="" return="" source="" }="">