??★,°:.☆( ̄▽ ̄)/$:.°★ ??
這篇文章主要介紹常用排序算法。
學(xué)其所用,用其所學(xué)。——梁?jiǎn)⒊?/font>
歡迎來到我的博客,一起學(xué)習(xí),共同進(jìn)步。
喜歡的朋友可以關(guān)注一下,下次更新不迷路??
??1. 算法介紹
排序算法是計(jì)算機(jī)科學(xué)中常見的一類算法,用于將一組數(shù)據(jù)按照特定的順序進(jìn)行排列。下面介紹幾種常見的排序算法:
- 冒泡排序(Bubble Sort):
- 從待排序序列的第一個(gè)元素開始,兩兩比較相鄰元素的大小,如果順序不對(duì)則交換位置。
- 每一輪結(jié)束后,最大(或最小)的元素會(huì)移動(dòng)到末尾。
- 時(shí)間復(fù)雜度:平均情況和最壞情況下為 O(n^2),最好情況下為 O(n)。
- 空間復(fù)雜度:O(1)。
- 插入排序(Insertion Sort):
- 將未排序序列的第一個(gè)元素插入已排序序列的正確位置。
- 從第二個(gè)元素開始,依次與前面的元素比較并插入到正確位置。
- 時(shí)間復(fù)雜度:平均情況和最壞情況下為 O(n^2),最好情況下為 O(n)。
- 空間復(fù)雜度:O(1)。
- 選擇排序(Selection Sort):
- 每一輪從待排序序列中選擇最?。ɑ蜃畲螅┑脑兀c當(dāng)前位置交換。
- 每一輪結(jié)束后,當(dāng)前位置之前的元素都是有序的。
- 時(shí)間復(fù)雜度:平均情況和最壞情況下為 O(n^2)。
- 空間復(fù)雜度:O(1)。
- 快速排序(Quick Sort):
- 選擇一個(gè)基準(zhǔn)元素,將序列分為比基準(zhǔn)小的元素和比基準(zhǔn)大的元素。
- 遞歸地對(duì)劃分后的子序列進(jìn)行快速排序。
- 時(shí)間復(fù)雜度:平均情況下為 O(nlogn),最壞情況下為 O(n^2)。
- 空間復(fù)雜度:平均情況下為 O(logn),最壞情況下為 O(n)。
- 歸并排序(Merge Sort):
- 將序列遞歸地拆分成兩個(gè)子序列,對(duì)子序列進(jìn)行排序,然后合并兩個(gè)有序子序列。
- 使用分治法思想,將排序問題分解為較小的子問題。
- 時(shí)間復(fù)雜度:平均情況下為 O(nlogn)。
- 空間復(fù)雜度:O(n)。
??2. C++實(shí)現(xiàn)
#include <iostream>
#include <cstdlib>
#include <ctime>
// 冒泡排序 bubbleSort 兩兩比較
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]) {
std::swap(arr[j], arr[j+1]);
}
}
}
}
// 選擇排序 selectionSort 選最小值
void selectionSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
int minIndex = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
std::swap(arr[i], arr[minIndex]);
}
}
// 插入排序 insertionSort 依次成序
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; 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;
}
}
// 歸并排序 mergeSort
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int* L = new int[n1];
int* R = new int[n2];
for (int i = 0; i < n1; i++) {
L[i] = arr[left + i];
}
for (int j = 0; j < n2; j++) {
R[j] = arr[mid + 1 + j];
}
int i = 0;
int j = 0;
int k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
delete[] L;
delete[] R;
}
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);
}
}
// 快速排序 quickSort
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i+1], arr[high]);
return i+1;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// 打印數(shù)組
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
}
int main() {
const int SIZE = 10;
// 生成隨機(jī)整數(shù)數(shù)組
int arr[SIZE];
srand(time(0));
for (int i = 0; i < SIZE; i++) {
arr[i] = rand() % 100; // 生成 0 到 99 的隨機(jī)數(shù)
}
std::cout << "Original array: ";
printArray(arr, SIZE);
// 使用冒泡排序進(jìn)行排序
bubbleSort(arr, SIZE);
std::cout << "Array after bubble sort: ";
printArray(arr, SIZE);
// 使用選擇排序進(jìn)行排序
selectionSort(arr, SIZE);
std::cout << "Array after selection sort: ";
printArray(arr, SIZE);
// 使用插入排序進(jìn)行排序
insertionSort(arr, SIZE);
std::cout << "Array after insertion sort: ";
printArray(arr, SIZE);
// 使用歸并排序進(jìn)行排序
mergeSort(arr, 0, SIZE-1);
std::cout << "Array after merge sort: ";
printArray(arr, SIZE);
// 使用快速排序進(jìn)行排序
quickSort(arr, 0, SIZE-1);
std::cout << "Array after quick sort: ";
printArray(arr, SIZE);
return 0;
}
編譯運(yùn)行:
g++ -o main main.cpp && ./main
文章來源:http://www.zghlxwxcb.cn/news/detail-626120.html
以上。文章來源地址http://www.zghlxwxcb.cn/news/detail-626120.html
到了這里,關(guān)于【C++】數(shù)據(jù)結(jié)構(gòu)與算法:常用排序算法的文章就介紹完了。如果您還想了解更多內(nèi)容,請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望大家以后多多支持TOY模板網(wǎng)!