/**
* file Sort.js
* ide:vscode JavaScript Sorting Algorithms
* 插件：IntelliSense,JSDoc,CodeLens,Debugger for Chrome,
静态代码检查：ESLint,JSHint,Flow Langugae Support,StandardJS-JavaScript Standard Style,
koroFileHeader(文件头注释),
测试插件：Mocha sidebar,Mocha Test Explorer,Jest
Path Intellisense,Import Cost,Quokka.js,Code Metrics,Javascript Booster,Turbo Console Log
* https://www.programiz.com/dsa/counting-sort
* https://www.geeksforgeeks.org/sorting-algorithms/
* https://thedukh.com/2021/02/javascript-sorting-algorithms-explained-radix-sort/
* https://www.epubit.com/
* https://www.ituring.com.cn/
*/
/**
* Description placeholder 1. Bubble Sort冒泡排序法
* @date 10/23/2023 - 2:47:05 PM
*
* @param {*} arry 需要排序的整数數組
* @param {*} nszie 数组长度
* @returns {*} 返回排序后结果的数组
*/
function BubbleSort(arry, nszie)
{
var i, j, temp;
var swapped;
for (i = 0; i < nszie - 1; i++)
{
swapped = false;
for (j = 0; j < nszie - i - 1; j++)
{
if (arry[j] > arry[j + 1])
{
// Swap arry[j] and arry[j+1]
temp = arry[j];
arry[j] = arry[j + 1];
arry[j + 1] = temp;
swapped = true;
}
}
// IF no two elements were
// swapped by inner loop, then break
if (swapped == false)
break;
}
return arry
}
/**
* 交换操作
* @param {*} arry 数组
* @param {*} xp
* @param {*} yp
*/
function swap(arry,xp, yp)
{
var temp = arry[xp];
arry[xp] = arry[yp];
arry[yp] = temp;
}
/**
* 2 选择排序 Selection Sort
* @param {*} arry 需要排序的整数數組
* @param {*} nsize 数组长度
* @returns 返回排序后结果的数组
*/
function SelectionSort(arry, nsize)
{
var i, j, min_idx;
// One by one move boundary of unsorted subarray
for (i = 0; i < nsize-1; i++)
{
// Find the minimum element in unsorted array
min_idx = i;
for (j = i + 1; j < nsize; j++)
if (arry[j] < arry[min_idx])
min_idx = j;
// Swap the found minimum element with the first element
swap(arry,min_idx, i);
}
return arry;
}
/**
* 3 插入排序 Insertion Sort
* @param {*} arry 需要排序的整数數組
* @param {*} nsize 数组长度
* @returns 返回排序后结果的数组
*/
function InsertionSort(arry, nsize)
{
let i, key, j;
for (i = 1; i < nsize; i++)
{
key = arry[i];
j = i - 1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arry[j] > key)
{
arry[j + 1] = arry[j];
j = j - 1;
}
arry[j + 1] = key;
}
return arry;
}
/**
* 整数数组转字符串显示
* @param {*} arry 需要打印的数组
* @param {*} nsize 数组的长度
*
* @returns 返回打印格式字符串
*/
function stringArray(arry, nsize)
{
var myStr=new Array();
var i;
for (i = 0; i < nsize; i++)
{
//getstr=getstr+arry[i].toString() + "<br/>";
myStr[i]=arry[i];
console.log(arry[i]);
}
console.log(myStr.join("<br/>"));
return myStr.join(" <br/>");
//console.log(arry);
/* var myStr=new Array();
var getstr="";
*/
/*
var i;
for (i = 0; i < nsize; i++)
{
getstr=getstr+arry[i] + " ";
myStr[i]=arry[i].toString();
console.log(myStr[i]);
}
return getstr;//myStr.join(" ");*/
}
//
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
/**
*
* @param {*} arry 需要打印的数组
* @param {*} indexStart
* @param {*} m
* @param {*} indexEnd
*/
function merge(arry, indexStart, m, indexEnd)
{
var n1 = m - indexStart + 1;
var n2 = indexEnd - m;
// Create temp arrays
var L = new Array(n1);
var R = new Array(n2);
// Copy data to temp arrays L[] and R[]
for (var i = 0; i < n1; i++)
L[i] = arry[indexStart + i];
for (var j = 0; j < n2; j++)
R[j] = arry[m + 1 + j];
// Merge the temp arrays back into arry[l..r]
// Initial index of first subarray
var i = 0;
// Initial index of second subarray
var j = 0;
// Initial index of merged subarray
var k = indexStart;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arry[k] = L[i];
i++;
}
else {
arry[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements of
// L[], if there are any
while (i < n1) {
arry[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of
// R[], if there are any
while (j < n2) {
arry[k] = R[j];
j++;
k++;
}
}
// l is for left index and r is
// right index of the sub-array
// of arr to be sorted
/**
* 4 合并排序 Merge Sort
* @param {*} arry 需要排序的整数數組
* @param {*} indexStart 数组索引值 0
* @param {*} indexEnd 索引值最大值 数组长度-1
* @returns 返回排序好的数组
*/
function mergeSort(arry,indexStart, indexEnd){
if(indexStart>=indexEnd){
return;
}
var m =indexStart+ parseInt((indexEnd-indexStart)/2);
mergeSort(arry,indexStart,m);
mergeSort(arry,m+1,indexEnd);
merge(arry,indexStart,m,indexEnd);
return arry;
}
/**
* Function to partition the array and return the partition index
* @param {*} arry 需要排序的整数數組
* @param {*} low 数组索引值 0
* @param {*} high 索引值最大值 数组长度-1
* @returns
*/
function quickPartition(arry, low, high) {
// Choosing the pivot
let pivot = arry[high];
// Index of smaller element and indicates the right position of pivot found so far
let i = low - 1;
for (let j = low; j <= high - 1; j++) {
// If current element is smaller than the pivot
if (arry[j] < pivot) {
// Increment index of smaller element
i++;
[arry[i], arry[j]] = [arry[j], arry[i]]; // Swap elements
}
}
[arry[i + 1], arry[high]] = [arry[high], arry[i + 1]]; // Swap pivot to its correct position
return i + 1; // Return the partition index
}
/**
* The main function that implements QuickSort
* 5 Quick Sort 快速排序
* @param {*} arry 需要排序的整数數組
* @param {*} low 数组索引值 0
* @param {*} high 索引值最大值 数组长度-1
* @returns 返回排序好的数组
*/
function quickSort(arry, low, high) {
if (low < high) {
// pi is the partitioning index, arr[pi] is now at the right place
let pi = quickPartition(arry, low, high);
// Separately sort elements before partition and after partition
quickSort(arry, low, pi - 1);
quickSort(arry, pi + 1, high);
}
return arry;
}
/**
* of Heap Sort
* 6 堆排序 Heap Sort
* @param {*} arry 需要排序的整数數組
* @returns 返回排序好的数组
*/
function heapSort( arry)
{
var N = arry.length;
// Build heap (rearrange array)
for (var i = Math.floor(N / 2) - 1; i >= 0; i--)
heapify(arry, N, i);
// One by one extract an element from heap
for (var i = N - 1; i > 0; i--) {
// Move current root to end
var temp = arry[0];
arry[0] = arry[i];
arry[i] = temp;
// call max heapify on the reduced heap
heapify(arry, i, 0);
}
return arry;
}
/**
* To heapify a subtree rooted with node i which is
* an index in arr[]. n is size of heap
* @param {*} arry 需要排序的整数數組
* @param {*} N 数组长度
* @param {*} i 数组索引值 0
*/
function heapify(arry, N, i)
{
var largest = i; // Initialize largest as root
var l = 2 * i + 1; // left = 2*i + 1
var r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < N && arry[l] > arry[largest])
largest = l;
// If right child is larger than largest so far
if (r < N && arry[r] > arry[largest])
largest = r;
// If largest is not root
if (largest != i) {
var swap = arry[i];
arry[i] = arry[largest];
arry[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arry, N, largest);
}
}
/**
* 7 Counting Sort 计数排序
* @param {*} arry 需要排序的整数數組
* @param {*} min 数组中最小的值
* @param {*} max 数组中最大的值
* @returns 返回排序好的数组
*/
function countingSort(arry, min, max) {
let j = 0;
let supplementary = [];
for (let i = min; i <= max; i++) {
supplementary[i] = 0;
}
for (let i=0; i < arry.length; i++) {
supplementary[arry[i]] += 1;
}
for (let i = min; i <= max; i++) {
while (supplementary[i] > 0) {
arry[j++] = i;
supplementary[i] -= 1;
}
}
return arry;
}
/**
* 7 Counting Sort 计数排序
* @param {*} arry 需要排序的整数數組
* @returns 返回排序好的数组
*/
function duCountingSort(arry) {
let j = 0;
let supplementary = [];
min=getArrayMin(arry);
max=getArrayMax(arry);
for (let i = min; i <= max; i++) {
supplementary[i] = 0;
}
for (let i=0; i < arry.length; i++) {
supplementary[arry[i]] += 1;
}
for (let i = min; i <= max; i++) {
while (supplementary[i] > 0) {
arry[j++] = i;
supplementary[i] -= 1;
}
}
return arry;
}
/**
* 求得数组中最大值
* @param {*} arry 整数數組
* @param {*} nszie 数组长度
* @returns 返回数组中的最大值
*/
function getMax(arry,nszie)
{
let mx = arry[0];
for (let i = 1; i < nszie; i++)
if (arry[i] > mx)
mx = arry[i];
return mx;
}
/**
* 求得数组中最小值
* @param {*} arry 整数數組
* @returns 返回数组中的最小值
*/
function getArrayMin(arry){
var min = arry[0];
for(var i = 1, ilen = arry.length; i < ilen; i+=1) {
if(arry[i] < min) {
min = arry[i];
}
}
return min;
}
/**
* 求得数组中最大值
* @param {*} arry 整数數組
* @returns 返回数组中的最大值
*/
function getArrayMax(arry) {
var max = arry[0];
for(var i = 1,ilen = arry.length; i < ilen; i++) {
if(arry[i] > max) {
max = arry[i];
}
}
return max;
}
/**
*
* @param {*} arry
* @param {*} nszie
* @param {*} exp
*/
function radixCountSort(arry,nszie,exp)
{
let output = new Array(nszie); // output array
let i;
let x;
let count = new Array(10);
for(let i=0;i<10;i++)
count[i]=0;
// Store count of occurrences in count[] 这里有问题
for (i = 0; i < nszie; i++)
{
let s=arry[i]/exp;
x = Math.floor(s) % 10;
}
count[x]++;
// Change count[i] so that count[i] now contains
// actual position of this digit in output[]
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
// Build the output array
for (i = nszie - 1; i >= 0; i--) {
output[count[x] - 1] = arry[i];
count[x]--;
}
// Copy the output array to arr[], so that arr[] now
// contains sorted numbers according to current digit
for (i = 0; i < nszie; i++)
arry[i] = output[i];
}
/**
* The main function to that sorts arr[] of size n using
8 Radix Sort 基数排序 Radix Sort 有问题
* @param {*} arry 需要排序的整数數組
* @param {*} nszie 数组长度
*/
function radixsort(arry,nszie)
{
// Find the maximum number to know number of digits
let m = getMax(arry, nszie);
// Do counting sort for every digit. Note that
// instead of passing digit number, exp is passed.
// exp is 10^i where i is current digit number
for (let exp = 1; Math.floor(m / exp) > 0; exp *= 10)
radixCountSort(arry, nszie, exp);
return arry;
}
/**
*
* @param {*} arry
* @returns
*/
function getBiggestDigitCount(arry) {
let maxDigits = 0;
for (let i = 0; i < arry.length; i++) {
maxDigits = Math.max(maxDigits, arry[i].toString().length);
}
return maxDigits;
}
/**
*
* @param {*} arry
* @param {*} i
* @returns
*/
function getDigitAtPlace(arry, i) {
return arry.toString().split("").reverse()[i] || 0;
}
/**
* 8 Radix Sort 基数排序
* @param {*} arry 需要排序的整数數組
* @returns 返回排序后结果的数组
*/
function DuRadixSort(arry) {
let maxDigits = getBiggestDigitCount(arry);
for (let i = 0; i < maxDigits; i++) {
let bucketArray = Array.from({ length: 10 }, () => []);
for (let j = 0; j < arry.length; j++) {
let digit = getDigitAtPlace(arry[j], i);
bucketArray[digit].push(arry[j]);
}
arry = [].concat(...bucketArray);
}
return arry;
}
/**
* 9. Bucket Sort 桶排序
* using bucket sort
* @param {*} arry 需要排序的整数數組
* @param {*} nszie 数组长度
* @returns 返回排序后结果的数组
*/
function bucketSort(arry,nszie)
{
if (nszie <= 0)
return;
// 1) Create n empty buckets
let buckets = new Array(nszie);
for (let i = 0; i < nszie; i++)
{
buckets[i] = [];
}
// 2) Put array elements in different buckets
for (let i = 0; i < nszie; i++) {
let idx = arry[i] * nszie;
let flr = Math.floor(idx);
//buckets[flr].push(arry[i]); //有问题
buckets[flr].push(arry[i]);
}
// 3) Sort individual buckets
for (let i = 0; i < nszie; i++) {
buckets[i].sort(function(a,b){return a-b;});
}
// 4) Concatenate all buckets into arr[]
let index = 0;
for (let i = 0; i < nszie; i++) {
for (let j = 0; j < buckets[i].length; j++) {
arry[index++] = buckets[i][j];
}
}
return arry;
}
/**
* 9. Bucket Sort 桶排序
* @param {*} arry 需要排序的整数數組
* @returns 返回排序后结果的数组
*/
function duBubbleSort(arry) {
let swapHappened;
for (let i = arry.length; i > 0; i--) {
swapHappened = true;
for (let j = 0; j < i - 1; j++) {
if (arry[j] > arry[j + 1]) {
[arry[j], arry[j + 1]] = [arry[j + 1], arry[j]];
swapHappened = false;
}
}
if (swapHappened) {
break;
}
}
return arry;
}
/**
*
* @param {*} arry
* @returns
*/
function bingoSort(arry) {
let n=arry.length;
let bingo = arry[0];
let nextBingo = arry[0];
// For finding the maximum and minimum element of
// the Array
for (let i = 1; i < n; bingo = Math.min(bingo, arry[i]), nextBingo = Math.max(nextBingo, arry[i]), i++)
;
let largestEle = nextBingo;
let nextElePos = 0;
while (bingo < nextBingo)
{
// Will keep the track of the element position to
// shifted to their correct position
let startPos = nextElePos;
for (let i = startPos; i < n; i++) {
if (arry[i] == bingo) {
[arry[i], arry[nextElePos]] = [arry[nextElePos], arry[i]];
nextElePos = nextElePos + 1;
}
// Here we are finding the next Bingo Element
// for the next pass
else if (arry[i] < nextBingo)
nextBingo = arry[i];
}
bingo = nextBingo;
nextBingo = largestEle;
}
for (let i = 0; i < arry.length; i++) {
// console.log("arr: ",arry[i]);
}
return arry;
}
/**
* 打印数组
* @param {*} arry 需要找印的数组
* @param {*} nsize 数组长度
* @returns 返回打印的格式字符串
*/
function printArray(arry, nsize)
{
var getstr="";
var i;
for (i = 0; i < nsize; i++)
{
console.log(arry[i] + " ");
getstr=getstr+arry[i]+" ";
}
return getstr;
}
调用：
<!--
* @Author: error: error: git config user.name & please set dead value or install git && error: git config user.email & please set dead value or install git & please set dead value or install git
* @Date: 2023-10-23 12:26:05
* @LastEditors: error: error: git config user.name & please set dead value or install git && error: git config user.email & please set dead value or install git & please set dead value or install git
* @LastEditTime: 2023-10-23 17:22:26
* @FilePath: \algorithms\1.html alt+ctrl+i 键
* @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
-->
<!doctype html>
<html>
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width,initial-scale=1.0,maximum-scale=1.0,minimum-scale=1.0,user-scalable=no">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<title>成长开始，geovindu,涂聚文，Geovin Du Bubble Sort冒泡排序法</title>
<meta name="Description" content="geovindu"/>
<meta name="Keywords" content="geovindu"/>
<meta name="author" content="geovindu"/>
<script src="js/jquery-3.6.0.js"></script>
<script src="js/SortAlgorithm/Sort.js"></script>
<script type="text/javascript">
$(document).ready(function () {
// 1. Bubble Sort冒泡排序法
var arry = [ 64, 34, 25, 112, 220, 11, 90 ];
var nzie= arry.length;
var duselect=SelectionSort(arry,nzie);
console.log(duselect)
var geovindu=BubbleSort(arry, nzie);
console.log(geovindu);
var inserttdu=InsertionSort(arry,nzie);
var myStr=new Array();
var i;
for (i = 0; i < nzie; i++)
{
//getstr=getstr+arry[i].toString() + "<br/>";
myStr[i]=geovindu[i].toString();
console.log(geovindu[i].toString());
}
console.log(myStr.join("<br/>"));
var du=stringArray(arry,nzie);
var du2=stringArray(duselect,nzie);
var du3=stringArray(inserttdu,nzie);
var dumergeSort=mergeSort(arry,0,nzie-1);
var du4=stringArray(dumergeSort,nzie);
console.log("mergesoft:"+dumergeSort);
var duQuick=quickSort(arry,0,nzie-1);
var du5=stringArray(duQuick,nzie);
var duHeap=heapSort(arry,0,nzie-1);
var du6=stringArray(duHeap,nzie-1);
var duCounting=duCountingSort(arry);
var du7=stringArray(duCounting,nzie);
let duarry=[170, 45, 75, 90, 802, 24, 2, 66];
var duradix=DuRadixSort(duarry);
var du8=stringArray(duradix,nzie);
let arrdu = [0.897, 0.565,
0.656, 0.1234,
0.665, 0.3434];
var dubucket=duBubbleSort(arrdu);
var du9=stringArray(dubucket,nzie);
var dubingo=bingoSort(arry);
var du10=stringArray(dubingo,nzie);
console.log("bucket Sort:"+dubucket);
console.log(du8);
console.log(du);
console.log("Bubble Sorted array: ");
var getstr=printArray(arry, nzie);
console.log("str:"+getstr)
$("#txtgeovindu").html(getstr);
txtgeovindu.innerHTML = getstr;//stringArray(geovindu,nsize);
$("#geovindu").html("1.泡冒泡排序Bubble Sorted：<br/>"+myStr.join("<br/>"));
$("#geovindu2").html(du);
$("#geovindu3").html("2.选择排序Selection Sorted：<br/>"+du2);
$("#geovindu4").html("3.插入排序Insertion Sorted：<br/>"+du3);
$("#geovindu5").html("4.合并排序 Merge Sort ：<br/>"+du4);
$("#geovindu6").html("5.快速排序 Quick Sort：<br/>"+du5);
$("#geovindu6").html("6.堆排序 Heap Sort：<br/>"+du6);
$("#geovindu7").html("7.计数排序 Counting Sort：<br/>"+du7);
$("#geovindu8").html("8.基数排序 Radix Sort：<br/>"+du8);
$("#geovindu9").html("9.桶排序 Bucket Sort：<br/>"+du9);
$("#geovindu10").html("10.宾果排序 Bingo Sort：<br/>"+du10);
});
</script>
</head>
<body>
<textarea id="txtgeovindu" class="geovindu" name="" cols="30" rows="10"></textarea>
<div id="geovindu"></div>
<div id="geovindu2"></div>
<div id="geovindu3"></div>
<div id="geovindu4"></div>
<div id="geovindu5"></div>
<div id="geovindu6"></div>
<div id="geovindu7"></div>
<div id="geovindu8"></div>
<div id="geovindu9"></div>
<div id="geovindu10"></div>
</body>
</html>
输出：
