C++排序算法

排序算法可以对数据进行有序排列,是计算机科学中一个重要的课题。C++标准库包含了多种常用排序算法,本文将介绍其中的几种实现方法。

一、简单排序

插入排序适用于小规模排序,直接插入元素到正确位置:

for(int i=1; i<len; ++i) {
  int key = arr[i];
  int j = i-1;
  while(j>=0 && arr[j]>key) {
    arr[j+1] = arr[j]; 
    j--;
  }
  arr[j+1] = key;
}

选择排序通过交换选择最小元素到正确位置:

for(int i=0; i<len-1; ++i) {
  int minIndex = i;
  for(int j=i+1; j<len; ++j) {
    if(arr[j] < arr[minIndex]) {
      minIndex = j;
    } 
  }
  swap(arr[i], arr[minIndex]);
}

二、高效排序

快速排序使用Partition递归区分元素,然后递归排序划分的区域:

int Partition(arr, left, right) {
  int pivot = arr[left];
  while(left < right) {
    while(arr[right] >= pivot && left < right) right--;
    arr[left] = arr[right];
    while(arr[left] <= pivot && left < right) left++; 
    arr[right] = arr[left];
  }
  arr[left] = pivot;
  return left;
}

void QuickSort(arr, left, right) {
  if(left < right) {
    int p = Partition(arr, left, right);
    QuickSort(arr, left, p-1);
    QuickSort(arr , p+1, right);
  }
}

三、STL排序函数

C++ STL提供了快速高效的排序函数,如sort、stable_sort等。

#include <algorithm>

sort(arr, arr+len); // 对数组排序
sort(vec.begin(), vec.end()); // vector排序 

掌握常见排序算法及其C++实现,是编写高效程序必备的能力,可以解决编码中的许多实际问题。