那些年，让我面试头大的几个排序算法，今天终于搞懂了！(带动画演示版)
那些年，让我面试头大的几个排序算法，今天终于搞懂了！(带动画演示版)
大家好，我是浩说
一想到那些年被问到怀疑人生的排序算法问题
满是心酸泪
于是痛定思痛
总结出7大排序算法的实现代码
以及生动的动画演示
保证你们每个人都能看得懂
看完去找面试官单挑
1.冒泡排序（Bubble Sort）
1.比较相邻的元素如果第一个比第二个大，就交换它们两个。 2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数; 3.针对所有的元素重复以上的步骤，除了最后一个; 4.重复步骤1〜3，直到排序完成。
function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i < len; i++) {
for (var j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j+1]) {
var temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
分享朋友圈，大家一起进步！
2.快速排序（Quick Sort）
1.从数列中挑出一个元素，称为“基准”（pivot）; 2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置这个称为分区（分区）操作。3.递归地（递归）把小于基准值元素的子数列和大于基准值元素的子数列排序。
function quickSort(arr, left, right) {
var len = arr.length,
partitionIndex,
left =typeof left !='number' ? 0 : left,
right =typeof right !='number' ? len - 1 : right;
if (left < right) {
partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex-1);
quickSort(arr, partitionIndex+1, right);
}
return arr;
}
function partition(arr, left ,right) {
var pivot = left,
index = pivot + 1;
for (var i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index-1;
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
3.插入排序（Insertion Sort）
1.从第一个元素开始，该元素可以认为已经被排序; 2.取出下一个元素，在已经排序的元素序列中从后向前扫描; 3.如果该元素（已排序）大于新元素，将该元素移到下一位置; 4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置; 5.将新元素插入到该位置后; 6.重复步骤2〜5。
function insertionSort(arr) {
var len = arr.length;
var preIndex, current;
for (var i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
return arr;
}
4.希尔排序（Shell Sort）
1.选择一个增量序列T1，T2，...，TK，其中TI> TJ，TK = 1; 2.按增量序列个数k，对序列进行k趟排序; 3.每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。
function shellSort(arr) {
var len = arr.length,
temp,
gap = 1;
while (gap < len / 3) {
gap = gap * 3 + 1;
}
for (gap; gap > 0; gap = Math.floor(gap / 3)) {
for (var i = gap; i < len; i++) {
temp = arr[i];
for (var j = i-gap; j > 0 && arr[j]> temp; j-=gap) {
arr[j + gap] = arr[j];
}
arr[j + gap] = temp;
}
}
return arr;
}
5.归并排序（Merge Sort）
1.把长度为Ñ的输入序列分成两个长度为N / 2的子序列; 2.对这两个子序列分别采用归并排序; 3.将两个排序好的子序列合并成一个最终的排序序列。
function mergeSort(arr) {
var len = arr.length;
if (len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
var result = [];
while (left.length>0 && right.length>0) {
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;
}
6.计数排序（Counting Sort）
1.找出待排序的数组中最大和最小的元素; 2.统计数组中每个值为我的元素出现的次数，存入数组Ç的第我项; 3.对所有的计数累加（从ç中的第一个元素开始，每一项和前一项相加）; 4.反向填充目标数组：将每个元素我放在新数组的第C（ⅰ）项，每放一个元素就将C（ⅰ）减去1。
function countingSort(arr, maxValue) {
var bucket =new Array(maxValue + 1),
sortedIndex = 0;
arrLen = arr.length,
bucketLen = maxValue + 1;
for (var i = 0; i < arrLen; i++) {
if (!bucket[arr[i]]) {
bucket[arr[i]] = 0;
}
bucket[arr[i]]++;
}
for (var j = 0; j < bucketLen; j++) {
while(bucket[j] > 0) {
arr[sortedIndex++] = j;
bucket[j]--;
}
}
return arr;
}
7.基数排序（Radix Sort）
1.取得数组中的最大数，并取得位数; 2.ARR为原始数组，从最低位开始取每个位组成基数数组; 3.对基数进行计数排序（利用计数排序适用于小范围数的特点）;
var counter = [];
function radixSort(arr, maxDigit) {
var mod = 10;
var dev = 1;
for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
for(var j = 0; j < arr.length; j++) {
var bucket = parseInt((arr[j] % mod) / dev);
if(counter[bucket]==null) {
counter[bucket] = [];
}
counter[bucket].push(arr[j]);
}
var pos = 0;
for(var j = 0; j < counter.length; j++) {
var value =null;
if(counter[j]!=null) {
while ((value = counter[j].shift()) !=null) {
arr[pos++] = value;
}
}
}
}
return arr;
}分享朋友圈，大家一起进步！
腾讯云开发者
