1.冒泡
for (var i = 0; i < arr.length - 1; i++) {
for (var j = 0; j < arr.length - i - 1; j++) {
if (arr[j + 1] < arr[j]) {
[ arr[j + 1] , arr[j] ] = [ arr[j] , arr[j + 1] ]
}
}
}
2.快速
if (arr.length < 2) {
return arr;
}
var a = Math.floor(arr.length / 2);
var b = arr.splice(a, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++) {
if (arr[i] < b) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quick(left).concat(b, quick(right))
}
3.插入排序
function cr(arr) {
for (var i = 1; i < arr.length; i++) {
// 把当前要比较的数储存起来
var a = arr[i];
for (var j = i - 1; j >= 0 && a < arr[j]; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = a;
}
return arr;
}
4.选择
function select() {
for (var i = 0; i < arr.length - 1; i++) {
var min_index = i;
for (var j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min_index]) {
min_index = j;
}
}
var min = arr[i];
arr[i] = arr[min_index];
arr[min_index] = min;
}
return arr;
}
5.归并排序
function so(arr) {
if (arr.length < 2) {
return arr;
}
var mid = Math.floor(arr.length / 2);
var left = arr.slice(0, mid);
var right = arr.slice(mid);
return ma(so(left), so(right))
}
function ma(left, right) {
var c = [];
while (left.length > 0 && right.length > 0) {
if (left[0] < right[0]) {
c.push(left.shift());
} else {
c.push(right.shift());
}
}
while (left.length > 0) {
c.push(left.shift());
} while (right.length > 0) {
c.push(right.shift());
}
return c;
}
6.希尔排序
function sell(arr) {
for (var gap = Math.floor(arr.length / 2); gap > 0; gap = Math.floor(gap / 2)) {
var a;
// 数组遍历 i从第一个增量开始 从后面的比前面的
for (var i = gap; i < arr.length; i++) {
// 定义一个变量储存当前的这个数
a = arr[i];
var j = i;
// gap不变 是数组前半段 a是gap后面的数
while (j - gap >= 0 && arr[j - gap] > a) {
arr[j] = arr[j - gap];
j = j - gap;
}
arr[j] = a;
}
}
return arr;
}
7.基数排序
var counter = [];
// maxDigit最大位数
function sort(arr, maxDigit) {
var mod = 10;
var dev = 1;
for (var i = 0; i < maxDigit; i++, mod *= 10, dev *= 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;
}
8.桶排序
function bucketSort(arr, bucketSize) {
if (arr.length === 0) {
return arr;
}
var i;
var minValue = arr[0];
var maxValue = arr[0];
for (i = 1; i < arr.length; i++) {
if (arr[i] < minValue) {
minValue = arr[i]; // 输入数据的最小值
} else if (arr[i] > maxValue) {
maxValue = arr[i]; // 输入数据的最大值
}
}
// 桶的初始化
var DEFAULT_BUCKET_SIZE = 5; // 设置桶的默认数量为5
bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
var buckets = new Array(bucketCount);
for (i = 0; i < buckets.length; i++) {
buckets[i] = [];
}
// 利用映射函数将数据分配到各个桶中
for (i = 0; i < arr.length; i++) {
buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
}
arr.length = 0;
for (i = 0; i < buckets.length; i++) {
insertionSort(buckets[i]); // 对每个桶进行排序，这里使用了插入排序
for (var j = 0; j < buckets[i].length; j++) {
arr.push(buckets[i][j]);
}
}
return arr;
}
9.计数排序
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;
}
10.堆排序
var len; // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量
function buildMaxHeap(arr) { // 建立大顶堆
len = arr.length;
for (var i = Math.floor(len / 2)-1; i >= 0; i--) {//以他的父节点来进行判断
//i ==取出来的父节点
heapify(arr, i);
console.log(i);
}
}
function heapify(arr, i) { // 堆调整
var left = 2 * i + 1,//左边子节点
right = 2 * i + 2,//右边子节点
largest = i;//把i当成大顶堆中的父节点
if (left < len && arr[left] > arr[largest]) {//不存在的节点排除
largest = left;//如果左边的子节点大于他的父节点 将其位置交换
}
if (right < len && arr[right] > arr[largest]) {
largest = right;//如果右边的子节点大于他的父节点 将其位置交换
}
if (largest != i) {//如果largest不等于i，说明他不大于他两个子节点中得其中一个
swap(arr, i, largest);//将位置交换
heapify(arr, largest);//重新调用该方法 已达到维护完全二叉树的性质
}
}
//交换位置方法
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function heapSort(arr) {
buildMaxHeap(arr);//建立新的大顶堆
//因为 排序后 最顶部已经是最大的数
//这里需要将第一位和最后一位的位置更换 将最后一位取出来
//这时候 就需要保证大顶堆的成立 则需要调用 堆调整的方法
// arr.length - 1 最后一位 0 为第一位(即最大值或者最小值)
for (var i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
len--;//每一次父级-1
heapify(arr, 0);//保证大顶堆的成立
}
return arr;
}
