0 最原始的排序
这里先把排序做一个分类，根据是否额外开辟空间分为内排序和外排序，其中内排序根据操作可以分为交换排序、选择排序、插入排序和周并排序。这是最早会的一种最low的排序方式，也属于交换排序
function theLowestSort(arr) {for (var i = 0; i < arr.length; i++) {for (var j = i + 1; j < arr.length; j++) {if (arr[i] > arr[j]) {var temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}}
}
复制代码1 冒泡排序(bubble sort)
// 冒泡排序属于交换排序 基本思想为相邻两两比较 后者小于前者则交换 这样小值一步一步交换到前列
function bubbleSort(arr) {for (var i = 0; i < arr.length; i++) {for (var j = arr.length - 1; j >= i; j--) {// 最后一位开始 依次与相邻元素比较和交换// 注意：永远是相邻元素！才是冒泡if (arr[j] > arr[j + 1]) {var temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}
复制代码2 简单选择排序(simple selection sort)
// 简单选择排序属于选择排序 基本思想为每次遍历都找出当前循环的最小项与第i位置元素交换 其交换次数远小于冒泡排序 所以效率高于冒泡
function simpleSelectionSort(arr) {for (var i = 0; i < arr.length; i++) {var min = i; // 由于i从0开始 先定义最小值是ifor (var j = i + 1; j < arr.length; j++) {if (arr[j] < arr[min]) {min = j; // 每当有元素更小 就用下标刷新min值}}if (i !== min) {var temp = arr[i];arr[i] = arr[min];arr[min] = temp;}}
}
复制代码3 直接插入排序(straight insertion sort)
// 直接插入排序属于插入排序 将数组分为两部分 前半部分有序 后半部分无序 依次选择无序部分第一项与前面有序部分比较 找到合适位置插入
function straightInsertionSort(arr) {// 假设第0个元素单独为有序 所以从第1个元素开始for (var i = 1; i < arr.length; i++) {if (arr[i] < arr[i - 1]) {var guard = arr[i]; // 当前项比前一项小 计划前移 先做一个标记var j = i - 1;arr[i] = arr[j]; // 前一项赋值到当前项 这是当前项挨个往前比较的开端while (j >= 0 && guard < arr[j]) {// 挨个往前比较 当前项比前一项大时跳出循环arr[j + 1] = arr[j]; // 从后往前遍历 每一项都往后一项赋值 整体后移j--;}arr[j + 1] = guard; // 标记赋值到当前项 由于while循环中j-- 需要j+1给加回来 即当前项arr[i]}}
}
复制代码以上1 2 3三种排序时间复杂度都是
未完待续。。。