選擇排序

選擇排序應(yīng)該是最容易被想到的排序方式吧
1.從頭開(kāi)始澡谭，與自己的后一位比較，如果小的就交換值
2.外層循環(huán)執(zhí)行 n-1 次即可

• 平均時(shí)間復(fù)雜度:O(n2)
• 最好情況復(fù)雜度:O(n2)
• 最壞情況復(fù)雜度:O(n2)

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 位置 逐個(gè)與 后面的元素進(jìn)行比較
                 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.從頭開(kāi)始相鄰兩個(gè)元素兩兩比較西剥，a[i] > a[i+1] 交換則交換兩者位置
2.每循環(huán)一次痹栖，即可確定一位

• 平均時(shí)間復(fù)雜度：O(n2)
• 最好情況復(fù)雜度: O(n)
• 最壞情況復(fù)雜度：O(n2)

 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.從頭開(kāi)始，逐個(gè)跟前一個(gè)元素對(duì)比
2.如果比前一個(gè)元素小瞭空，即交換兩個(gè)元素的位置揪阿，交換的次數(shù)比較多

• 平均時(shí)間復(fù)雜度：O(n2)
• 最好情況復(fù)雜度：O(n)
• 最壞情況復(fù)雜度: O(n2)

 void insertSort(int *arr,int count){
    for(int i = 0; i < count; i++){    // 一共循環(huán)的次數(shù)
        for(int j = i; j>0;j--){      //從當(dāng)前 i 的位置與前一個(gè)對(duì)比
            if(arr[j] < arr[j-1]){    // 如果后者小于前者，則交換咆畏，否則結(jié)束當(dāng)前循環(huán)進(jìn)入下一次南捂。
                int temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }else{
                break;
        } 
    }
}

歸并排序

所謂 歸并 是指將若干個(gè)已排好序的部分合并成一個(gè)有序的部分。

• 平均時(shí)間復(fù)雜度：O( n log n)
• 最好情況復(fù)雜度：O( n log n)
• 最差情況復(fù)雜度：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++;
       }
}

快速排序

快排是現(xiàn)有排序算法中最快的
1.選擇一個(gè)值旧找，將數(shù)組中比該值大的都放到該值右側(cè)溺健，小的都放到左側(cè)
2.以該值的位置將數(shù)組分割成左右兩個(gè)部分，分別對(duì)左右兩個(gè)部分執(zhí)行上一步操作

• 平均時(shí)間復(fù)雜度：O(n log n)
• 最好情況復(fù)雜度: O(n log n)
• 最壞情況復(fù)雜度: O(n2)

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;
}