c++中八大排序算法

本文介绍的是C++中八大排序算法，分别是冒泡排序、选择排序、插入排序、快速排序、希尔排序、归并排序、堆排序和计数排序。下面将对这八种算法进行详细讲解。

冒泡排序

冒泡排序（Bubble Sort），是一种简单的排序算法。它重复地遍历要排序的列表，比较每对相邻的项，如果它们的顺序错误就把它们交换过来。遍历列表的工作是重复地进行知道没有再需要交换，也就是列表已经排序完成。

冒泡排序的优点是操作简单易实现，缺点是时间复杂度较高，只适合于小规模的数据排序。

下面是C++的冒泡排序代码实现：

void bubbleSort(int arr[], int n){
  for(int i = 0; i < n-1; i++){
    for(int j = 0; j < n-i-1; j++){
      if(arr[j] > arr[j+1]){
        // 交换arr[j]和arr[j+1]
        int tmp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = tmp;
      }
    }
  }
}

选择排序

选择排序（Selection Sort）是一种简单直观的排序算法。它每次找到最小值，然后放到待排序数组的起始位置，直到全部数组排序完成。

选择排序和冒泡排序一样，时间复杂度也较高，适合小规模数据排序。

下面是C++的选择排序代码实现：

void selectionSort(int arr[], int n){
  int minIndex;
  for(int i = 0; i < n-1; i++){
    minIndex = i;
    for(int j = i+1; j < n; j++){
      if(arr[j] < arr[minIndex]){
        minIndex = j;
      }
    }
    // 交换arr[i]和arr[minIndex]
    int tmp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = tmp;
  }
}

插入排序

插入排序（Insertion Sort）每次排一个数组项，以此方式构建最后的排序数组。假设这个算法已经排序了第1,2,...i-1 个元素，新的第i个元素继承自原数组中的第i个元素。然后它向前面扫描，将所有大于它的元素后移一个位置，为它留下正确的位置。

插入排序相较于前两种排序算法，其操作性能会更好一些。

下面是C++的插入排序代码实现：

void insertionSort(int arr[], int n){
  for(int i = 1; i < n; i++){
    int current = arr[i];
    int j = i;
    while(j > 0 && arr[j-1] > current){
      arr[j] = arr[j-1];
      j--;
    }
    arr[j] = current;
  }
}

快速排序

快速排序（Quick Sort）使用分治策略来把一个序列分为两个子序列，根据情况递归地排序每个子序列。具体步骤为： 1.从序列中挑出一个元素，称为"基准"（pivot）； 2.重新排列序列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的可以任意一边）。     这个称为分区 (partition) 算法； 3.递归地（recursively）把小于基准值元素的子序列和大于基准值元素的子序列排序。

快速排序的时间复杂度O(nlogn)通常比其他排序算法的最优时间复杂度还要更快，因此被广泛使用。不足之处在于排序的稳定性，并且在随机数据集上性能表现优秀，在特定的数据集上性能表现较差。

下面是C++的快速排序代码实现：

void quickSort(int arr[], int left, int right){
  int i, j, pivot;
  if(left < right){
    i = left;
    j = right;
    pivot = arr[left];
    while(i < j){
      while(i < j && arr[j] >= pivot) j--;
      if(i < j) arr[i++] = arr[j];
      while(i < j && arr[i] < pivot) i++;
      if(i < j) arr[j--] = arr[i];
    }
    arr[i] = pivot;
    quickSort(arr, left, i-1);
    quickSort(arr, i+1, right);
  }
}

希尔排序

希尔排序（Shell Sort）是由Donald Shell在1959年发明的，也称"缩小增量排序"。希尔排序的主要思想是将原始序列分割成若干子序列，然后对子序列排序，使得原始序列中的任意两个相距较远的元素在子序列中都能够比较到。然后依次缩小增量，继续以上步骤，最后增量为1。

希尔排序的时间复杂度是O(n^1.3)，比直接插入排序的时间复杂度O(n^2)优秀，但是并不稳定。

下面是C++的希尔排序代码实现：

void shellSort(int arr[], int n){
  int gap, i, j;
  int tmp;
  for(gap = n/2; gap > 0; gap /= 2){
    for(i = gap; i < n; i++){
      tmp = arr[i];
      for(j = i; j >= gap && arr[j-gap] > tmp; j -= gap){
        arr[j] = arr[j-gap];
      }
      arr[j] = tmp;
    }
  }
}

归并排序

归并排序（Merge Sort）是一种有效的排序算法，采用分治算法的一个典型应用。该算法的实现需要用到递归，在拆分数据的过程中很容易地将其划分为一个一个小的子数组，每个子数组都可以视为已排序好的。

归并排序在操作大数据集合时有很高的效率，能够维持其稳定性。但其缺点在于空间复杂度高。

下面是C++的归并排序代码实现：

void mergeSort(int arr[], int start, int end){
  if(start < end){
    int mid = (start + end) / 2;
    mergeSort(arr, start, mid);
    mergeSort(arr, mid+1, end);
    Merge(arr, start, mid, end);
  }
}

void Merge(int arr[], int start, int mid, int end){
  int i = start;
  int j = mid + 1;
  int k = 0;
  int* tmp = new int[end - start + 1];
  while(i <= mid && j <= end){
    if(arr[i] < arr[j]){
      tmp[k++] = arr[i++];
    }
    else{
      tmp[k++] = arr[j++];
    }
  }
  while(i <= mid){
    tmp[k++] = arr[i++];
  }
  while(j <= end){
    tmp[k++] = arr[j++];
  }
  for(int l = 0; l < k; l++){
    arr[start+l] = tmp[l];
  }
  delete[] tmp;
}

堆排序

堆排序（Heap Sort）是一种树形选择排序，是一种改良的选择排序。可以利用数组的特点快速定位指定序列中的最大值（或最小值）。堆排序分为两个过程，建立堆和排序两个过程。建立堆的时间复杂度是O(n)，排序的时间复杂度是O(nlogn)，堆排序是一种不稳定的排序方法。

下面是C++的堆排序代码实现：

void heapSort(int arr[], int n){
  for(int i = n/2-1; i >= 0; i--){
    adjustHeap(arr, i, n);
  }
  for(int i = n-1; i >= 1; i--){
    swap(arr[0], arr[i]);
    adjustHeap(arr, 0, i);
  }
}

void adjustHeap(int arr[], int i, int len){
  int tmp = arr[i];
  for(int k = i*2+1; k < len; k = k*2+1){
    if(k+1 < len && arr[k] < arr[k+1]) k++;
    if(arr[k] > tmp){
      arr[i] = arr[k];
      i = k;
    }
    else{
      break;
    }
  }
  arr[i] = tmp;
}

计数排序

计数排序（Counting Sort）是一种非比较排序算法，通过对每个元素出现的次数进行计数统计，根据统计结果来进行排序。计数排序的时间复杂度为O(n)，非常高效，但是需要耗费额外的内存空间来存储计数器。

下面是C++的计数排序代码实现：

void countingSort(int arr[], int len){
  int minVal = arr[0];
  int maxVal = arr[0];
  for(int i = 1; i < len; i++){
    if(arr[i] < minVal) minVal = arr[i];
    if(arr[i] > maxVal) maxVal = arr[i];
  }
  int cntLen = maxVal - minVal + 1;
  int* cntArr = new int[cntLen];
  memset(cntArr, 0, sizeof(int)*cntLen);
  for(int i = 0; i < len; i++){
    cntArr[arr[i] - minVal]++;
  }
  int index = 0;
  for(int i = 0; i < cntLen; i++){
    while(cntArr[i] > 0){
      arr[index] = i + minVal;
      cntArr[i]--;
      index++;
    }
  }
  delete[] cntArr;
}

至此，C++中的八大排序算法就讲解完毕。