【JavaScript案例】——运用JS实现排序算法中的冒泡排序
以前我们讲过使用Python实现排序算法中的冒泡排序,今天我们来看看使用JS怎么实现排序算法中的冒泡排序.
那么什么是排序算法呢?
排序的概念:
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
</head>
<body>
<script>
window.onload = function () {
var arr = [18, 9, 21, 47, 15, 23, 11];
// 外层循环控制的是比较的轮数
for (var i = 0; i < arr.length - 1; i++) {
// 内层循环是每一轮的两两比较
for (var j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
var temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
console.log(arr);
}
</script>
</body>
</html>
选择排序
题型：int[]array= {3,4,2,1}; 将这个数组从小到大排序。
思路：
1.我们先得到一个最小的数，将它放置于数组第一位。
2.然后我们按照第一步，每一次得到一个最小数放置在第二位直到放到倒数第二位。（最后一位不用再去得到放置）
3.然后我们就要去考虑怎么样得到最小然后去放置。
比喻：有一个拳击手，刚开始带着这个数字装备去打擂台，当他打赢了以后，对方说不公平，让其互换数字装备继续下一次打擂，直到拳击手的数字装备最差，才承认他的技术。（从当前开始的后一个一直打到最后一个得到最小值）
4.分解：
第一次：3 4 2 1 得到3去进行打擂；
3 4 2 1–>（3和4比）3 4 2 1–>（3和2比）2 4 3 1–>（2和1比）1 4 3 2
第二次：1 4 3 2 得到4去进行打擂；
1 4 3 2–>（4和3比）1 3 4 2–>（3和2比）1 2 4 3
第三次:1 2 4 3得到4去进行打擂；
1 2 4 3–>（4和3比）1 2 3 4 (尽量自己画一遍，帮助理解)
5.上代码分析
int[]array= {3,4,2,1}; //创建任意一个数组
int length=array.length; //先得到数组长度
for(int i=0;i<length-1;i++) { //从0位置开始放置最小值
//这个for循环主要是为了不同的放置，放置到0,1，length-1；
for(int j=i+1;j<length;j++) { //对0位置（i）之后的数依次进行比较
//j=i+1就是因为打擂台是从下一个开始到结束
if(array[i]>array[j]) { //如果array[i]的数大于比较的数,就进行交换
int num=array[i]; //交换
array[i]=array[j];
array[j]=num;
}
}
}
for(int res:array) { //增强for循环
System.out.print(res+" "); //输出
}
6.结果
总结：其实选择排序重要的是理清思路，然后对于双for的语句，要去思考它的控制语句和判断条件，观察前后for里面i ，j是否有关联。
题目：冒泡排序一个队列（升序）
程序分析（个人分析仅供参考）：
首先，我们要知道这个排序是怎么样排序的。
按照升序排列，言外之意就是从小到大排列数字
拿第一个数字举例，他需要做的判断是几次呢？
首先，第一个数字需要跟第二个数字做对比，如果第一个数字比第二个数字大，那么两个数字交换一下位置，以此类推。
总结下来就是第一个循环需要对比的次数是list的长度-1，
第二个循环所需要对比的次数list长度-1-第一个循环的次数m。
第二个循环的主要功能就是具体判断两个数值的大小，以及一个交换的功能。
交换，可以像我这样直接写一个交换功能的函数，也可以直接写到for循环中。当然这个要根据个人的习惯
使用第二个循环的参数n当作list的角标进行判断list中的数值，
通过已经写好的交换功能函数，把原本list中的数值进行替换为更新后的数值。
最后输出更新后的数值，这样就实现了一个冒泡排序的功能
转载于:https://www.cnblogs.com/AngesZhu/p/7520230.html
<val,idx>,每个数个角标和值作为二元组，然后排序。这个题目还有很多东西可以挖掘，比如如果进行数据离散化怎么做，以及用树状数组做等等，留作日后复习做着用。
class Solution {
private:
struct Node{
int l=0,r=0,sum=0;
};
vector<Node> a;
void build(int p,int l,int r){
int mid = (l+r)/2;
a[p].l = l;
a[p].r = r;
if(l==r) return;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
}
void update(int p,int val){
if(a[p].l == a[p].r){
a[p].sum++;
return;
}
int mid = (a[p].l + a[p].r)/2;
if(val<=mid){
update(p*2,val);
}else{
update(p*2+1,val);
}
a[p].sum++;
}
int query(int p,int l,int r){
if(l<=a[p].l && r>=a[p].r ){
return a[p].sum;
}
int res = 0 , mid = (a[p].l+a[p].r)/2;
if(l<=mid){
res += query(p*2,l,r);
}
if(r>mid){
res += query(p*2+1,l,r);
}
return res;
}
public:
vector<int> ans;
vector<pair<int,int>> temp;
vector<int> countSmaller(vector<int>& nums) {
int n = nums.size();
if(n==0) return ans;
a.resize(4*n);
ans.resize(n);
build(1,1,n);
for(int i=0;i<n;i++){
temp.push_back(make_pair(nums[i],i+1));
}
sort(temp.begin(),temp.end());
for(auto p:temp){
ans[ p.second-1 ] = query(1,p.second+1,n);
update(1,p.second);
}
return ans;
}
};
const int N = 20010;
class Solution {
void add(int x){
while(x<N){
c[x]++;
x += x&-x;
}
}
int ask(int x){
int res = 0;
while(x){
res += c[x];
x -= x&-x;
}
return res;
}
int c[N] = {0};
public:
vector<int> countSmaller(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n);
for(int& x:nums) x += 10001;
for(int i=n-1;i>=0;i--){
ans[i] = ask(nums[i]-1);
add(nums[i]);
}
return ans;
}
};
不得不说，树状数组比线段树的代码简洁多了。
