冒泡
n 次比較相鄰兩數并交換找到最值，然后 n-1 次比較找到次值……較小的數字像氣泡一樣浮出，
這里我引入flag排除：已經有序卻一直遍歷
function bubbleSort(arr){
const n=arr.length;
let flag=1,i,j;
for(i=0;i<n-1&&flag;i++){
//最壞的情況需要依次比較出最小值、次小值、次次小值
flag=0;//如果交換了就變
for(j=0;j<n-i-1;j++){
if(arr[j]>arr[j+1]){
const swap=arr[j];
arr[j]=arr[j+1];
arr[j+1]=swap;
flag=1;
}
}
}
return arr;
}
簡單選擇排序
和冒泡原理相似，但是少了很多交換，多了一個暫存最值的空間，
n 次比較相鄰兩數后最多只交換一次將最值放到位置上，然后 n-1 次比較找到次值
冒泡更適合基本有序的序列
function selectSort(arr)
{
const n=arr.length;
let i,j,minIndex;
for(i=0;i<n-1;i++){
minIndex=i;//先決定誰最小
for(j=i+1;j<n;j++){
if(arr[j]<arr[minIndex]){
minIndex=j;
}
}
if(minIndex!=i){
const swap=arr[i];
arr[i]=arr[minIndex];
arr[minIndex]=swap;
}
}
return arr;
}
直接插入
維護一個漸長的有序佇列
function insertSort(arr)
{
const n=arr.length;
let i,j,k;
for (i = 1; i < n; i++)
{
// a[i]插入前面的有序區間a[0...i-1]
for (j = i - 1; j >= 0; j--){
if (arr[j] < arr[i])break;
}
//這里有兩種可能，需要插入前面、不需要
if (j != i - 1){//需要插入
//后移一位，空出位置給arr[i]
const temp = arr[i];
for (k = i - 1; k > j; k--)
arr[k + 1] = arr[k];
//將a[i]放到正確位置上
arr[k + 1] = temp;
}
}
return arr;
}
希爾排序（進階版插入）
相比直接插入，多了一個維度，
利用gap劃分小組
gap由大變小
每個小組進行直接插入排序
注意呀，JavaScript除法沒有默認取整，需要借助parseInt方法
function shellSort(arr)
{
const n=arr.length;
let i, j, gap;
for (gap =parseInt(n/2); gap> 0; gap=parseInt(gap/2)){//依次縮小比較間隙
for (i = gap; i < n; i++){//gap分組
for (j = i - gap; j >= 0 && arr[j] > arr[j + gap]; j -= gap){//每個分組進行插入排序
console.log("j:"+j);
const temp=arr[j + gap];
arr[j + gap]=arr[j];
arr[j]=temp;
}
}
}
return arr;
}
快速排序
平均時間復雜度=O(n logn)
序列基本有序狀態時，快速排序退化為O(n^2)
function quick_part(arr,left,right){
//留下left和right后面遞回
var l = left;
var r = right;
var basic= arr[left]; //arr[left]即basic的原位置
if(left >= right){ //如果陣列只有一個元素
return;
}
while(l!=r){//兩者相遇，意味著一直到找到basic的位置
while(arr[r] > basic && l < r){ //l<r隨時注意嚴格控制哨兵不能錯過，從右邊向左找第一個比key小的數，找到或者兩個哨兵相碰，跳出回圈
r--;
}
while(arr[l] <= basic && l < r){ //這里的=號保證在本輪回圈結束前，key的位置不變，否則的話跳出回圈，交換l和left的位置的時候，left位置的上元素有可能不是key
l++;
}
//1、兩個哨兵到找到了目標值，2、j哨兵找到了目標值，3、兩個哨兵都沒找到(key是當前陣列最小值)
if(l!=r){ //交換兩個元素的位置
const swap = arr[l];
arr[l] = arr[r];
arr[r] = swap;
}
}
arr[left] = arr[l] //arr[left]即basic的原位置
arr[l] = basic;
quick_part(arr,left,l-1);
quick_part(arr,l+1,right);
}
function quickSort(arr){
quick_part(arr,0,arr.length-1);
}
歸并排序
function merge(left,right){
var temp=[];
while(left.length&&right.length){//取小的
if(left[0]<right[0]){
temp.push(left.shift());
}else{
temp.push(right.shift());
}
}
console.log("s："+temp);
//left和right長度不一樣時，直接連接剩下的長的部分（本身有序）
return temp.concat(left,right);
}
function mergeSort(arr){
if(arr.length<=1){
return arr;//打破后面return中的遞回，有回傳值了就去執行merge
}
var mid=Math.floor(arr.length/2);//
var left=arr.slice(0,mid);
var right=arr.slice(mid);
i++;
console.log(i+":"+left+right);
return merge(mergeSort(left),mergeSort(right));
}
堆排序
JavaScript的除法不是整除，另外提供了不同的取整方法
大頂堆的分析：
- 陣列映射堆的下標分析
- 程序分析（結合代碼）
大頂堆的代碼實作
var len; //全域的len,控制大頂堆的長度，實作在原陣列上的調整
function swap(arr, i, j) {
const temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function heapSort(arr) {
//通用方法
function maxHeapify(arr, i) { //調整以i為根的樹為大頂堆，
var left = 2*i+1,
right = 2*i+2,
largest = i; //暫定根節點最大
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) { //當該樹不知三個節點的時候，如果做出了調整可能破壞了子的大頂堆，需要條件遞回
swap(arr, i, largest); //交換最大的為父節點
maxHeapify(arr, largest); //交換后，原值arr[i]（往下降了）（索引保存為largest）
//作為根時，子節點可能比它大，因此要繼續調整
//往下查看
}
}
//構建大頂堆
function buildMaxHeap(arr) { //對每一個節點（非葉節點），做堆調整
len = arr.length;
//從最后一個有子節點開始，構建是自底向上的
for (var i = Math.floor(len/2)-1; i>=0; i--) {
maxHeapify(arr, i);
}
}
//輸出順序，并不斷維持大頂堆
function orderQ(arr) {
//把最大的數放到最后，然后全域len--=》讓大頂堆減少一個數，再調整維持大頂堆
for (var i = arr.length-1; i > 0; i--) {
swap(arr, 0, i);
len--;
maxHeapify(arr, 0);
}
}
buildMaxHeap(arr);
orderQ(arr);
return arr;
}
同理小頂堆的代碼：
var len; //全域的len,控制大頂堆的長度，實作在原陣列上的調整
function swap(arr, i, j) {
const temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function heapSort(arr) {
//通用方法
function minHeapify(arr, i) { //調整以i為根的樹為大頂堆，
var left = 2*i+1,
right = 2*i+2,
minest = i; //暫定根節點最大
if (left < len && arr[left] <arr[minest]) {
minest = left;
}
if (right < len && arr[right] <arr[minest]) {
minest = right;
}
if (minest != i) { //當該樹不知三個節點的時候，如果做出了調整可能破壞了子的大頂堆，需要條件遞回
swap(arr, i, minest); //交換最大的為父節點
minHeapify(arr, minest); //交換后，原值arr[i]（往下降了）（索引保存為largest）
//作為根時，子節點可能比它大，因此要繼續調整
//往下查看
}
}
//構建大頂堆
function buildMinHeap(arr) { //對每一個節點（非葉節點），做堆調整
len = arr.length;
//從最后一個有子節點開始，構建是自底向上的
for (var i = Math.floor(len/2)-1; i>=0; i--) {
minHeapify(arr, i);
}
}
//輸出順序，并不斷維持大頂堆
function orderQ(arr) {
//把最大的數放到最后，然后全域len--=》讓大頂堆減少一個數，再調整維持大頂堆
for (var i = arr.length-1; i > 0; i--) {
swap(arr, 0, i);
len--;
minHeapify(arr, 0);
}
}
buildMinHeap(arr);
orderQ(arr);
return arr;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/282635.html
標籤：其他
上一篇：Spring Boot——通過原始碼探究靜態資源的映射規則
下一篇：Vue 官網學習筆記