掌握C++中的常用排序算法

常用排序算法介绍

排序算法是计算机科学中的基础算法之一。常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、归并排序等。在本文中,我们将介绍 C++ 中的常用排序算法及其实现。

冒泡排序

算法原理

冒泡排序是一种简单的排序算法。它会多次遍历待排序的数组,每次比较相邻的两个元素,如果顺序不对则交换它们的位置,直到所有元素都排好序。

以下是冒泡排序的 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]){

swap(arr[j], arr[j+1]);

}

}

}

}

冒泡排序的时间复杂度为 O(n^2)。

选择排序

算法原理

选择排序是一种简单的排序算法。它会首先在待排序的数组中找到最小的元素,将其放在第一个位置,然后在剩余的元素中再找到最小的元素,放在第二个位置,依此类推。

以下是选择排序的 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;

}

}

swap(arr[i], arr[minIndex]);

}

}

选择排序的时间复杂度为 O(n^2)。

插入排序

算法原理

插入排序是一种简单的排序算法。它会将待排序的数组分为已排序和未排序两部分,首先将第一个元素看作已排序部分,然后将后面的元素一个一个地插入到已排序部分中,直到所有元素都排好序。

以下是插入排序的 C++ 实现:

void insertionSort(int arr[], int n){

int j, temp;

for (int i = 1; i < n; i++){

j = i-1;

temp = arr[i];

while (j >= 0 && arr[j] > temp){

arr[j+1] = arr[j];

j--;

}

arr[j+1] = temp;

}

}

插入排序的时间复杂度为 O(n^2)。

快速排序

算法原理

快速排序是一种常用的排序算法。它的核心思想是选择一个基准元素,将后面的元素分为两部分,一部分是小于基准元素的,另一部分是大于基准元素的,然后递归地对这两部分元素进行排序。

以下是快速排序的 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);

}

}

快速排序的时间复杂度为 O(nlogn)。

归并排序

算法原理

归并排序是一种常用的排序算法。它的核心思想是将一个数组分成两部分,分别对这两部分进行排序,然后将这两部分再合并起来。具体而言,它将待排序数组不断地对半划分,直到每个子数组都只有一个元素,然后将这些子数组两两合并,直到最终只剩下一个完整的有序数组。

以下是归并排序的 C++ 实现:

void merge(int arr[], int left, int mid, int right){

int i, j, k;

int n1 = mid - left + 1;

int n2 = right - mid;

int L[n1], R[n2];

for (i = 0; i < n1; i++){

L[i] = arr[left+i];

}

for (j = 0; j < n2; j++){

R[j] = arr[mid+1+j];

}

i = 0;

j = 0;

k = left;

while (i < n1 && j < n2){

if (L[i] <= R[j]){

arr[k++] = L[i++];

}

else{

arr[k++] = R[j++];

}

}

while (i < n1){

arr[k++] = L[i++];

}

while (j < n2){

arr[k++] = R[j++];

}

}

void mergeSort(int arr[], int left, int right){

if (left < right){

int mid = left + (right-left)/2;

mergeSort(arr, left, mid);

mergeSort(arr, mid+1, right);

merge(arr, left, mid, right);

}

}

归并排序的时间复杂度为 O(nlogn)。

总结

本文介绍了 C++ 中常用的排序算法及其实现,这些算法包括冒泡排序、选择排序、插入排序、快速排序和归并排序。这些排序算法各有优缺点,各有适应场景。在实际应用中,我们可以根据需要选择合适的排序算法。

免责声明:本文来自互联网,本站所有信息(包括但不限于文字、视频、音频、数据及图表),不保证该信息的准确性、真实性、完整性、有效性、及时性、原创性等,版权归属于原作者,如无意侵犯媒体或个人知识产权,请来电或致函告之,本站将在第一时间处理。猿码集站发布此文目的在于促进信息交流,此文观点与本站立场无关,不承担任何责任。

后端开发标签