基本排序算法
1.冒泡排序
| 核心原理: | 数组两个相邻元素比较大小，交换位置 |
|---|---|
| 步骤1: | 比较相邻的元素。如果第一个比第二个大，就交换他们两个。 |
| 步骤2: | 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 |
| 步骤3: | 针对所有的元素重复以上的步骤，除了最后一个。 |
| 步骤4: | 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 |
image
示例代码：
arr = [10,24,15,17,43,26,34]
function bubbleSort(arr){
//1.外层循环:控制需要比较的元素(如:第一次排序后，最后一个元素就不需要比较了)
for(var i = 1;i < arr.length;i++){
//2.内层循环:负责两两元素比较，将元素放到正确位置上
// 内层循环与外层循环的关系:j<arr.length-i(比如数组有4个元素,第0下标的元素只要比较3次;第1下标的元素比较2次)
for(var j = 0;j < arr.length-i;j++){
//3.打擂台，声明第三变量辅助排序
if(arr[j] > arr[j+1]){
var temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}
console.log(bubbleSort(arr));//[10, 15, 17, 24, 26, 34, 43]
2.插入法排序
| 核心原理: | 将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据 |
|---|---|
| 步骤1: | 从第一个元素开始，该元素可以认为已经被排序 |
| 步骤2: | 取出下一个元素，在已经排序的元素序列中从后向前扫描 |
| 步骤3: | 如果该元素（已排序）大于新元素，将该元素移到下一位置 |
| 步骤4: | 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置 |
| 步骤5: | 将新元素插入到该位置后重复步骤 2~4 |
image
示例代码：
arr = [10,24,15,17,43,26,34]
function insertSort(arr){
//第一个元素被认为已经被排序,从第二个元素，即下标为1的元素开始
for(var i = 1;i < arr.length;i++){
//未排序的元素，与其前面已排序的元素，两两进行比较
for(var j = i;j >= 0;j--){
//如果前面的某个元素大于该排序元素，排序元素前移
if(arr[j-1] > arr[j]){
temp = arr[j]
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}
return arr;
}
console.log(insertSort(arr));//[10, 15, 17, 24, 26, 34, 43]
3.选择排序
| 核心原理: | 从待排序数组中选择一个最小（或最大）数字，放入新数组中 |
|---|---|
| 步骤1: | 从第一个元素开始，假设该元素为最小 |
| 步骤2: | 通过循环将该元素与其它未排序的元素对比，找出未排序的最小元素 |
| 步骤3: | 如果未排序的某个元素才是最小，与该元素互换位置 |
| 步骤4: | 重复步骤 1-3，直到完成 |
image
示例代码：
arr = [10, 24, 15, 17, 43, 26, 34]
function selectSort(arr) {
for (var i = 0; i < arr.length - 1; i++) {
var minIndex = i;
minValue = arr[minIndex];
for (j = i + 1; j < arr.length; j++) {
if (arr[j] < minValue) {
minIndex = j
minValue = arr[minIndex];
}
}
//交换位置
temp = arr[i];
arr[i] = minValue;
arr[minIndex] = temp;
}
return arr;
}
console.log(selectSort(arr));//[10, 15, 17, 24, 26, 34, 43]
以上三种排序算法个人觉得比较好用，除此之外还有快速排序、归并排序，大家可以自己再去了解
本文同步发表在我的个人博客：https://www.lubaojun.com/
网友评论