常见排序算法

时间复杂度和空间复杂度

• O(1) 常数

• O(n) 线性

• O(n^2) 平方

• O(n^3)立方

• O（n!）阶乘

• O(logn) 对数

• O(nlogn)

• O(2^) 指数

• 时间复杂度顺序从小到大的顺序O(1)<O(log n) < O(n )< O(nlogn) < O(n^2) <O(n^3) < O(2^n) <O(n!) < O(n^n)

排序分类以及时间复杂度

快速排序（挖坑埋数 + 分治法）

blog参考

• 初始化 i= i， j =r，x = a[i]，取数组第一个数作为基准数

• j--,找出小与基准数的数据，挖出来，放到默认的第一个坑中；

• i++找出大于等于基准数的值，放到刚才的坑中；

• 重复2，3操作，当i==j中的话，把基准数放入其中

• 求出第一个基准数后，然后递归基准数的左边，基准数的右边

   void quick_sort(int s[], int l, int r)
    {
        if (l < r)
        {
            int i = l, j = r, x = s[l];
            while (i < j)
            {
                while(i < j && s[j] >= x) {// 从右向左找第一个小于x的数
                    j--;
                }
                if(i < j) {
                    s[i++] = s[j];
                }

                while(i < j && s[i] < x) {// 从左向右找第一个大于等于x的数
                    i++;
                }
                if(i < j) {
                    s[j--] = s[i];
                }
            }
            s[i] = x;
            quick_sort(s, l, i - 1); // 递归调用 
            quick_sort(s, i + 1, r);
        }
    }

冒泡排序

 void bubbleSort(int arr[]){

       if(arr==null || arr.length < 2 ){
           return;
       }

       for (int i = 0; i < arr.length; i++) {
           for (int j = 0; j < arr.length - i - 1 ; j++) {
               if(arr[j] > arr[j+1]){
                   int temp = arr[j];
                   arr[j] = arr[j+1];
                   arr[j+1] = temp;
               }
           }
       }

   }

三色旗问题

blog参考