冒泡排序算法【重要】

目录
冒泡排序算法：
时间复杂度
以下是具体的代码演示：

冒泡排序算法：

比较相邻的元素。如果第一个比第二个大，就交换它们两个
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数
针对所有的元素重复以上的步骤，除了最后一个
重复步骤1~3，直到排序完成

冒泡排序算法【重要】 - 图1

时间复杂度

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值：C(min)=n-1,M(min)=0.
所以，冒泡排序最好的时间复杂度为O(n);
若初始文件是反序的，需要进行n-1趟排序，每趟排序要进行(n-1-i)次关键字的比较，其中【0≤i≤n-1,i表示正在第几趟】
,且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：
比较次数，i=0表示最大趟n-1：
冒泡排序算法【重要】 - 图2
移动次数：
冒泡排序算法【重要】 - 图3
冒泡排序的最坏时间复杂度为O(n^2)

以下是具体的代码演示：

function sortArray(arr) {
    let tmp;
    for (let i = 0; i < arr.length-1;i++) {
        for(let j = 0 ; j < arr.length-1-i;j++){
            if(arr[j] > arr[j+1]){
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}

改进1：设置标志位pos，和是否交换排序操作标记flag；
每一层排完序之后，就记录排到最大的哪一位在什么位置，因为每一层最大的数就是它所在数组的倒数的位数,下一次就没必要再循环一遍。
假如已经排序好了的话，flag就是0，就直接return返回出去。

void ArraySort(int* arr,int size){
    int k=size-1;   //k用来记录每趟排序的最大的交换位置
    int pos=0;      //pos记录最后一次交换的位置
    for(int i=0;i<size-1;i++){
        int flag=0; //每一趟前都将flag标志先置为0 
        //每一趟排序都是从0~k，k初始是size-1，之后随着循环k值可能变化 
        for(int j=0;j<k;j++){
            if(arr[j]>arr[j+1]){
                int temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
                flag=1; //元素发生了交换，flag置为1 
                pos=j;  //pos存放循环里最后一次交换的位置j 
            }
        }
        k=pos;  //下一内层循环仅循环到0到这次得到的k之间 
        if(flag==0){
            //如果一趟下来flag没有变化，即元素本来就是有序，就直接return
            return;
        }
    }
}

原文来源
 参考其他
%23%23%23%20%E7%9B%AE%E5%BD%95%0A%5Btoc%5D%0A%20%20%0A%0A%23%23%23%20%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%EF%BC%9A%0A%0A-%20%E6%AF%94%E8%BE%83%E7%9B%B8%E9%82%BB%E7%9A%84%E5%85%83%E7%B4%A0%E3%80%82%E5%A6%82%E6%9E%9C%E7%AC%AC%E4%B8%80%E4%B8%AA%E6%AF%94%E7%AC%AC%E4%BA%8C%E4%B8%AA%E5%A4%A7%EF%BC%8C%E5%B0%B1%E4%BA%A4%E6%8D%A2%E5%AE%83%E4%BB%AC%E4%B8%A4%E4%B8%AA%0A-%20%E5%AF%B9%E6%AF%8F%E4%B8%80%E5%AF%B9%E7%9B%B8%E9%82%BB%E5%85%83%E7%B4%A0%E4%BD%9C%E5%90%8C%E6%A0%B7%E7%9A%84%E5%B7%A5%E4%BD%9C%EF%BC%8C%E4%BB%8E%E5%BC%80%E5%A7%8B%E7%AC%AC%E4%B8%80%E5%AF%B9%E5%88%B0%E7%BB%93%E5%B0%BE%E7%9A%84%E6%9C%80%E5%90%8E%E4%B8%80%E5%AF%B9%EF%BC%8C%E8%BF%99%E6%A0%B7%E5%9C%A8%E6%9C%80%E5%90%8E%E7%9A%84%E5%85%83%E7%B4%A0%E5%BA%94%E8%AF%A5%E4%BC%9A%E6%98%AF%E6%9C%80%E5%A4%A7%E7%9A%84%E6%95%B0%0A-%20%E9%92%88%E5%AF%B9%E6%89%80%E6%9C%89%E7%9A%84%E5%85%83%E7%B4%A0%E9%87%8D%E5%A4%8D%E4%BB%A5%E4%B8%8A%E7%9A%84%E6%AD%A5%E9%AA%A4%EF%BC%8C%E9%99%A4%E4%BA%86%E6%9C%80%E5%90%8E%E4%B8%80%E4%B8%AA%0A-%20%E9%87%8D%E5%A4%8D%E6%AD%A5%E9%AA%A41~3%EF%BC%8C%E7%9B%B4%E5%88%B0%E6%8E%92%E5%BA%8F%E5%AE%8C%E6%88%90%0A%0A!%5B33a947c71ad62b254cab62e5364d2813.gif%5D(evernotecid%3A%2F%2FD2915699-A379-4AAB-999E-4534E3EAFB1A%2Fappyinxiangcom%2F25807730%2FENResource%2Fp5)%0A%0A%23%23%23%20%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%0A%E8%8B%A5%E6%96%87%E4%BB%B6%E7%9A%84%E5%88%9D%E5%A7%8B%E7%8A%B6%E6%80%81%E6%98%AF%E6%AD%A3%E5%BA%8F%E7%9A%84%EF%BC%8C%E4%B8%80%E8%B6%9F%E6%89%AB%E6%8F%8F%E5%8D%B3%E5%8F%AF%E5%AE%8C%E6%88%90%E6%8E%92%E5%BA%8F%E3%80%82%E6%89%80%E9%9C%80%E7%9A%84%E5%85%B3%E9%94%AE%E5%AD%97%E6%AF%94%E8%BE%83%E6%AC%A1%E6%95%B0C%E5%92%8C%E8%AE%B0%E5%BD%95%E7%A7%BB%E5%8A%A8%E6%AC%A1%E6%95%B0M%E5%9D%87%E8%BE%BE%E5%88%B0%E6%9C%80%E5%B0%8F%E5%80%BC%EF%BC%9AC(min)%3Dn-1%2CM(min)%3D0.%0A%E6%89%80%E4%BB%A5%EF%BC%8C%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F%E6%9C%80%E5%A5%BD%E7%9A%84%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E4%B8%BAO(n)%3B%0A%0A%E8%8B%A5%E5%88%9D%E5%A7%8B%E6%96%87%E4%BB%B6%E6%98%AF%E5%8F%8D%E5%BA%8F%E7%9A%84%EF%BC%8C%E9%9C%80%E8%A6%81%E8%BF%9B%E8%A1%8C%3Cu%3En-1%3C%2Fu%3E%E8%B6%9F%E6%8E%92%E5%BA%8F%EF%BC%8C%E6%AF%8F%E8%B6%9F%E6%8E%92%E5%BA%8F%E8%A6%81%E8%BF%9B%E8%A1%8C(%3Cu%3En-1%3C%2Fu%3E-i)%E6%AC%A1%E5%85%B3%E9%94%AE%E5%AD%97%E7%9A%84%E6%AF%94%E8%BE%83%EF%BC%8C%E5%85%B6%E4%B8%AD%E3%80%900%E2%89%A4i%E2%89%A4n-1%2Ci%E8%A1%A8%E7%A4%BA%E6%AD%A3%E5%9C%A8%E7%AC%AC%E5%87%A0%E8%B6%9F%E3%80%91%0A%C2%A0%2C%E4%B8%94%E6%AF%8F%E6%AC%A1%E6%AF%94%E8%BE%83%E9%83%BD%E5%BF%85%E9%A1%BB%E7%A7%BB%E5%8A%A8%E8%AE%B0%E5%BD%95%E4%B8%89%E6%AC%A1%E6%9D%A5%E8%BE%BE%E5%88%B0%E4%BA%A4%E6%8D%A2%E8%AE%B0%E5%BD%95%E4%BD%8D%E7%BD%AE%E3%80%82%E5%9C%A8%E8%BF%99%E7%A7%8D%E6%83%85%E5%86%B5%E4%B8%8B%EF%BC%8C%E6%AF%94%E8%BE%83%E5%92%8C%E7%A7%BB%E5%8A%A8%E6%AC%A1%E6%95%B0%E5%9D%87%E8%BE%BE%E5%88%B0%E6%9C%80%E5%A4%A7%E5%80%BC%EF%BC%9A%0A%0A%E6%AF%94%E8%BE%83%E6%AC%A1%E6%95%B0%EF%BC%8Ci%3D0%E8%A1%A8%E7%A4%BA%E6%9C%80%E5%A4%A7%E8%B6%9Fn-1%EF%BC%9A%0A!%5Bf5123458dd98557f965946fb99c8cf8c.png%5D(evernotecid%3A%2F%2FD2915699-A379-4AAB-999E-4534E3EAFB1A%2Fappyinxiangcom%2F25807730%2FENResource%2Fp7)%0A%E7%A7%BB%E5%8A%A8%E6%AC%A1%E6%95%B0%EF%BC%9A%0A!%5B62dae5fd5b83a5d28cfec8a3ae72ca9e.png%5D(evernotecid%3A%2F%2FD2915699-A379-4AAB-999E-4534E3EAFB1A%2Fappyinxiangcom%2F25807730%2FENResource%2Fp6)%0A%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F%E7%9A%84%E6%9C%80%E5%9D%8F%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E4%B8%BAO(n%5E2)%0A%C2%A0%0A%0A%23%23%23%20%E4%BB%A5%E4%B8%8B%E6%98%AF%E5%85%B7%E4%BD%93%E7%9A%84%E4%BB%A3%E7%A0%81%E6%BC%94%E7%A4%BA%EF%BC%9A%0A%20%20%0A%0A%60%60%60%0Afunction%20sortArray(arr)%20%7B%0A%09let%20tmp%3B%0A%09for%20(let%20i%20%3D%200%3B%20i%20%3C%20arr.length-1%3Bi%2B%2B)%20%7B%0A%09%09for(let%20j%20%3D%200%20%3B%20j%20%3C%20arr.length-1-i%3Bj%2B%2B)%7B%0A%09%09%09if(arr%5Bj%5D%20%3E%20arr%5Bj%2B1%5D)%7B%0A%09%09%09%09tmp%20%3D%20arr%5Bj%5D%3B%0A%09%09%09%09arr%5Bj%5D%20%3D%20arr%5Bj%2B1%5D%3B%0A%09%09%09%09arr%5Bj%2B1%5D%20%3D%20tmp%3B%0A%09%09%09%7D%0A%09%09%7D%0A%09%7D%0A%7D%0A%60%60%60%0A%0A%0A%E6%94%B9%E8%BF%9B1%EF%BC%9A%E8%AE%BE%E7%BD%AE%E6%A0%87%E5%BF%97%E4%BD%8Dpos%EF%BC%8C%E5%92%8C%E6%98%AF%E5%90%A6%E4%BA%A4%E6%8D%A2%E6%8E%92%E5%BA%8F%E6%93%8D%E4%BD%9C%E6%A0%87%E8%AE%B0flag%EF%BC%9B%0A%E6%AF%8F%E4%B8%80%E5%B1%82%E6%8E%92%E5%AE%8C%E5%BA%8F%E4%B9%8B%E5%90%8E%EF%BC%8C%E5%B0%B1%E8%AE%B0%E5%BD%95%E6%8E%92%E5%88%B0%E6%9C%80%E5%A4%A7%E7%9A%84%E5%93%AA%E4%B8%80%E4%BD%8D%E5%9C%A8%E4%BB%80%E4%B9%88%E4%BD%8D%E7%BD%AE%EF%BC%8C%E5%9B%A0%E4%B8%BA%E6%AF%8F%E4%B8%80%E5%B1%82%E6%9C%80%E5%A4%A7%E7%9A%84%E6%95%B0%E5%B0%B1%E6%98%AF%E5%AE%83%E6%89%80%E5%9C%A8%E6%95%B0%E7%BB%84%E7%9A%84%E5%80%92%E6%95%B0%E7%9A%84%E4%BD%8D%E6%95%B0%2C%E4%B8%8B%E4%B8%80%E6%AC%A1%E5%B0%B1%E6%B2%A1%E5%BF%85%E8%A6%81%E5%86%8D%E5%BE%AA%E7%8E%AF%E4%B8%80%E9%81%8D%E3%80%82%0A%E5%81%87%E5%A6%82%E5%B7%B2%E7%BB%8F%E6%8E%92%E5%BA%8F%E5%A5%BD%E4%BA%86%E7%9A%84%E8%AF%9D%EF%BC%8Cflag%E5%B0%B1%E6%98%AF0%EF%BC%8C%E5%B0%B1%E7%9B%B4%E6%8E%A5return%E8%BF%94%E5%9B%9E%E5%87%BA%E5%8E%BB%E3%80%82%0A%0A%60%60%60%0Avoid%20ArraySort(int%20arr%2Cint%20size)%7B%0A%20%20%20%20int%20k%3Dsize-1%3B%20%20%20%2F%2Fk%E7%94%A8%E6%9D%A5%E8%AE%B0%E5%BD%95%E6%AF%8F%E8%B6%9F%E6%8E%92%E5%BA%8F%E7%9A%84%E6%9C%80%E5%A4%A7%E7%9A%84%E4%BA%A4%E6%8D%A2%E4%BD%8D%E7%BD%AE%0A%20%20%20%20int%20pos%3D0%3B%20%20%20%20%20%20%2F%2Fpos%E8%AE%B0%E5%BD%95%E6%9C%80%E5%90%8E%E4%B8%80%E6%AC%A1%E4%BA%A4%E6%8D%A2%E7%9A%84%E4%BD%8D%E7%BD%AE%0A%0A%20%20%20%20for(int%20i%3D0%3Bi%3Csize-1%3Bi%2B%2B)%7B%0A%20%20%20%20%20%20%20%20int%20flag%3D0%3B%20%2F%2F%E6%AF%8F%E4%B8%80%E8%B6%9F%E5%89%8D%E9%83%BD%E5%B0%86flag%E6%A0%87%E5%BF%97%E5%85%88%E7%BD%AE%E4%B8%BA0%20%0A%20%20%20%20%20%20%20%20%2F%2F%E6%AF%8F%E4%B8%80%E8%B6%9F%E6%8E%92%E5%BA%8F%E9%83%BD%E6%98%AF%E4%BB%8E0~k%EF%BC%8Ck%E5%88%9D%E5%A7%8B%E6%98%AFsize-1%EF%BC%8C%E4%B9%8B%E5%90%8E%E9%9A%8F%E7%9D%80%E5%BE%AA%E7%8E%AFk%E5%80%BC%E5%8F%AF%E8%83%BD%E5%8F%98%E5%8C%96%20%0A%20%20%20%20%20%20%20%20for(int%20j%3D0%3Bj%3Ck%3Bj%2B%2B)%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20if(arr%5Bj%5D%3Earr%5Bj%2B1%5D)%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20temp%3Darr%5Bj%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20arr%5Bj%5D%3Darr%5Bj%2B1%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20arr%5Bj%2B1%5D%3Dtemp%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20flag%3D1%3B%20%2F%2F%E5%85%83%E7%B4%A0%E5%8F%91%E7%94%9F%E4%BA%86%E4%BA%A4%E6%8D%A2%EF%BC%8Cflag%E7%BD%AE%E4%B8%BA1%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20pos%3Dj%3B%20%20%2F%2Fpos%E5%AD%98%E6%94%BE%E5%BE%AA%E7%8E%AF%E9%87%8C%E6%9C%80%E5%90%8E%E4%B8%80%E6%AC%A1%E4%BA%A4%E6%8D%A2%E7%9A%84%E4%BD%8D%E7%BD%AEj%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20k%3Dpos%3B%20%20%2F%2F%E4%B8%8B%E4%B8%80%E5%86%85%E5%B1%82%E5%BE%AA%E7%8E%AF%E4%BB%85%E5%BE%AA%E7%8E%AF%E5%88%B00%E5%88%B0%E8%BF%99%E6%AC%A1%E5%BE%97%E5%88%B0%E7%9A%84k%E4%B9%8B%E9%97%B4%20%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20if(flag%3D%3D0)%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%E5%A6%82%E6%9E%9C%E4%B8%80%E8%B6%9F%E4%B8%8B%E6%9D%A5flag%E6%B2%A1%E6%9C%89%E5%8F%98%E5%8C%96%EF%BC%8C%E5%8D%B3%E5%85%83%E7%B4%A0%E6%9C%AC%E6%9D%A5%E5%B0%B1%E6%98%AF%E6%9C%89%E5%BA%8F%EF%BC%8C%E5%B0%B1%E7%9B%B4%E6%8E%A5return%0A%20%20%20%20%20%20%20%20%20%20%20%20return%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%7D%0A%60%60%60%0A%0A%0A%20%20%0A%0A%5B%E5%8E%9F%E6%96%87%E6%9D%A5%E6%BA%90%5D(https%3A%2F%2Fblog.csdn.net%2Fu013270347%2Farticle%2Fdetails%2F80604690)%0A%0A%5B%E5%8F%82%E8%80%83%E5%85%B6%E4%BB%96%5D(https%3A%2F%2Fblog.csdn.net%2Fhansionz%2Farticle%2Fdetails%2F80822494)%0A%0A%0A

目录