常用排序

选择排序

选择排序应该是最容易被想到的排序方式吧
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;
}