C++库函数排序：常用排序算法及实现方法 |21xrx.com

C++库函数排序：常用排序算法及实现方法

2023-07-01 04:20:07 深夜i 9 0

C++库函数排序算法实现方法常用排序算法实现

C++是一种广泛使用的编程语言，在C++中，库函数的排序算法是非常常见和有用的。排序算法可以帮助我们将数据以一种特定的顺序进行排列，使得我们可以更快地进行数据搜索和查找。

在C++中，我们可以使用STL库中的一些排序函数来实现排序算法。常见的排序算法包括快速排序、归并排序、堆排序、插入排序和选择排序。下面是这些算法的详细解释和实现方法。

1. 快速排序（Quick Sort）

快速排序是最常用和最快的排序算法之一。该算法将数据分成两个部分，然后重复这个过程，直到排序完成。具体实现方法是选取一个主元素（pivot），然后将比主元素小的元素移动到左边，比主元素大的元素移动到右边。然后对左右两个部分递归调用快速排序函数即可。

实现方法：

void quicksort(int left, int right){
  int i = left;
  int j = right;
  int temp;
  int pivot = data[(left + right) / 2];
  /* partition */
  while (i <= j) {
    while (data[i] < pivot) i++;
    while (data[j] > pivot) j--;
    if (i <= j) {
      temp = data[i];
      data[i] = data[j];
      data[j] = temp;
      i++;
      j--;
    }
  }
  /* recursion */
  if (left < j) quicksort(left, j);
  if (i < right) quicksort(i, right);
}

2. 归并排序（Merge Sort）

归并排序是一种分治算法，也是一种比较快的排序算法。该算法的实现方法是将数组分成两半，然后将左右两半分别排序，最后将两部分合并起来即可。

实现方法：

void merge(int left, int mid, int right)
{
  int i, j, k;
  int n1 = mid - left + 1;
  int n2 = right - mid;
  /* create temp arrays */
  int L[n1], R[n2];
  /* Copy data to temp arrays L[] and R[] */
  for (i = 0; i < n1; i++)
    L[i] = data[left + i];
  for (j = 0; j < n2; j++)
    R[j] = data[mid + 1+ j];
  /* Merge the temp arrays back into data[left..right]*/
  i = 0;
  j = 0;
  k = left;
  while (i < n1 && j < n2)
  {
    if (L[i] <= R[j])
    {
      data[k] = L[i];
      i++;
    }
    else
    {
      data[k] = R[j];
      j++;
    }
    k++;
  }
  /* Copy the remaining elements of L[], if there are any */
  while (i < n1)
  {
    data[k] = L[i];
    i++;
    k++;
  }
  /* Copy the remaining elements of R[], if there are any */
  while (j < n2)
  {
    data[k] = R[j];
    j++;
    k++;
  }
}
/* left is for left index and right is right index of the sub-array of arr to be sorted */
void mergesort(int left, int right)
{
  if (left < right)
  {
    int mid = left+(right-left)/2;
    /* Sort first and second halves */
    mergesort(left, mid);
    mergesort(mid+1, right);
    merge(left, mid, right);
  }
}

3. 堆排序（Heap Sort）

堆排序是一种利用堆数据结构来排序的算法，是比较快的排序算法之一。该算法的实现方法是先将数据放入堆中，然后不断取出最大值或最小值来排序。

实现方法：

/* To heapify a subtree rooted with node i which is an index in arr[] */
void heapify(int arr[], int n, int i)
{
  int largest = i; // Initialize largest as root
  int l = 2*i + 1; // left = 2*i + 1
  int r = 2*i + 2; // right = 2*i + 2
  /* If left child is larger than root */
  if (l < n && arr[l] > arr[largest])
    largest = l;
  /* If right child is larger than largest so far */
  if (r < n && arr[r] > arr[largest])
    largest = r;
  /* If largest is not root */
  if (largest != i)
  {
    swap(arr[i], arr[largest]);
    /* Recursively heapify the affected sub-tree */
    heapify(arr, n, largest);
  }
}
/* main function to do heap sort */
void heapsort(int arr[], int n)
{
  /* Build heap (rearrange array) */
  for (int i = n / 2 - 1; i >= 0; i--)
    heapify(arr, n, i);
  /* One by one extract an element from heap */
  for (int i=n-1; i>=0; i--)
  {
    /* Move current root to end */
    swap(arr[0], arr[i]);
    /* call max heapify on the reduced heap */
    heapify(arr, i, 0);
  }
}

4. 插入排序（Insertion Sort）

插入排序是一种简单的排序算法，它的实现方法是将每个元素插入到前面已经排好序的数组中，不断重复这个过程。

实现方法：

void insertionsort(int arr[], int n)
{
  int i, key, j;
  for (i = 1; i < n; i++)
  {
    key = arr[i];
    j = i - 1;
    /* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */
    while (j >= 0 && arr[j] > key)
    {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
}

5. 选择排序（Selection Sort）

选择排序是一种简单的排序算法，它的实现方法是在数组中选择最小的元素，然后将它放在数组的最前面。然后再从剩下的元素中选择最小的元素，重复这个过程。

实现方法：

void selectionsort(int arr[], int n)
{
  int i, j, min_idx;
  /* One by one move boundary of unsorted subarray */
  for (i = 0; i < n-1; i++)
  {
    /* Find the minimum element in unsorted array */
    min_idx = i;
    for (j = i+1; j < n; j++)
      if (arr[j] < arr[min_idx])
        min_idx = j;
    /* Swap the found minimum element with the first element */
    swap(arr[min_idx], arr[i]);
  }
}

以上是五种常见的排序算法及其实现方法，你可以根据自己的需求来选择合适的排序算法。在实际的开发过程中，你也可以使用现成的STL库中的排序函数来快速完成排序任务。

上一篇: idea打包java可执行jar包

下一篇: C++库：定义常量和函数模块的集合

评论区

相似文章