美文网首页
常用排序

常用排序

作者: 琦均煞Sylar | 来源:发表于2017-10-07 18:35 被阅读0次

    选择排序

    选择排序应该是最容易被想到的排序方式吧
    1.从头开始,与自己的后一位比较,如果小的就交换值
    2.外层循环执行 n-1 次即可

    • 平均时间复杂度:O(n²)
    • 最好情况复杂度:O(n²)
    • 最坏情况复杂度:O(n²)
    void selectSort(int *arr, int count){
            for (int i = 0; i < count -1; i++){        // count - 1 次即可完成排序
                  for(int j = i+1; j < count; j++){    // 从 i 位置 逐个与 后面的元素进行比较
                     if(arr[i] >= arr[j]) continue;
                       arr[i] = arr[i] + arr[j];       // 交换
                       arr[j] = arr[i] - arr[j];
                       arr[i] = arr[i] - arr[j];
                  }
            }
    }
    

    冒泡排序

    1.从头开始相邻两个元素两两比较,a[i] > a[i+1] 交换则交换两者位置
    2.每循环一次,即可确定一位

    • 平均时间复杂度:O(n²)
    • 最好情况复杂度: O(n)
    • 最坏情况复杂度:O(n²)
     void bubbleSort(int *arr, int count){
        for(int i = 0; i < count; i++){
             for(int j = 0; j < count - 1 - i; j++){
                    if (arr[j] < arr[j+1]){
                        int temp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = temp;
                  }
            }
        }
    }
    

    插入排序

    貌似扑克牌整理顺序
    1.从头开始,逐个跟前一个元素对比
    2.如果比前一个元素小,即交换两个元素的位置,交换的次数比较多

    • 平均时间复杂度:O(n²)
    • 最好情况复杂度:O(n)
    • 最坏情况复杂度: O(n²)
     void insertSort(int *arr,int count){
        for(int i = 0; i < count; i++){    // 一共循环的次数
            for(int j = i; j>0;j--){      //从当前 i 的位置与前一个对比
                if(arr[j] < arr[j-1]){    // 如果后者小于前者,则交换,否则结束当前循环进入下一次。
                    int temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }else{
                    break;
            } 
        }
    }
    

    归并排序

    所谓 归并 是指将若干个已排好序的部分合并成一个有序的部分。

    • 平均时间复杂度:O( n log n)
    • 最好情况复杂度:O( n log n)
    • 最差情况复杂度:O( n log n)
    void mergeSort(int *total, int *arr_A, int length_A, int *arr_B, int length_B){
            int i = 0;
            int j = 0;
            while( i < length_A && j < length_B){
                  if( arr_A[i] < arr_B[j] ){
                      total[ i + j ] = arr_A[i++];
                    }else{
                      total[ i+j ] = arr_B[j++];
                    }
    
            while(i<length_A){
                  total[ i+j ] = arr_A[i];
                  i++;
            }
    
            while(j < length_B){
                  total [ i + j ] = arr_B[j];
                  j++;
           }
    }
    

    快速排序

    快排是现有排序算法中最快的
    1.选择一个值,将数组中比该值大的都放到该值右侧,小的都放到左侧
    2.以该值的位置将数组分割成左右两个部分,分别对左右两个部分执行上一步操作

    • 平均时间复杂度:O(n log n)
    • 最好情况复杂度: O(n log n)
    • 最坏情况复杂度: O(n²)
    void quickSort(int *arr, int leftIndex, int rightIndex){
          if (leftIndex >= rightIndex) return;
           int kp = keyPoint(arr,leftIndex,rightIndex);
            quickSort(leftIndex,kp-1);
            quickSort(kp+1,rightIndex);
    }
    
    int keyPoint(int *arr, int leftIndex,int rightIndex){
          int l = leftIndex;
          int r = rightIndex;
          int key = arr[i];
          while(l < r){
              while( l < r && arr[r] > key) r--;
              if (l < r){
                arr[l++] = arr[r];
               }
              while(l < r && arr[l] < key) l++;
              if (l < r){
                  arr[r--] = arr[l];
              }
              arr[l] = key;
          }
        return l;
    }
    

    相关文章

      网友评论

          本文标题:常用排序

          本文链接:https://www.haomeiwen.com/subject/kwtsyxtx.html