wordpress中文伪静态,北京网站关键词优化推荐,北京排名前10的公关公司,建设银行怎么网站定制短信通知在数据结构中#xff0c;排序是一个重要的操作#xff0c;它有助于提高数据的可读性和可操作性。排序算法有多种#xff0c;各有优缺点#xff0c;适用于不同的场景。以下是八大经典排序算法的介绍#xff1a;
1. 冒泡排序#xff08;Bubble Sort#xff09;
原理排序是一个重要的操作它有助于提高数据的可读性和可操作性。排序算法有多种各有优缺点适用于不同的场景。以下是八大经典排序算法的介绍
1. 冒泡排序Bubble Sort
原理通过重复遍历要排序的数组每次比较相邻的两个元素如果它们的顺序错误就交换它们的位置。这样最大的元素会逐步“冒泡”到数组的末尾。
时间复杂度O(n^2)
代码示例
void bubbleSort(std::vectorint arr) {int n arr.size();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]);}}}
}2. 选择排序Selection Sort
原理每次从未排序部分选择最小的元素放到已排序部分的末尾。
时间复杂度O(n^2)
代码示例
void selectionSort(std::vectorint arr) {int n arr.size();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]);}
}3. 插入排序Insertion Sort
原理构建有序序列对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。
时间复杂度O(n^2)
代码示例
void insertionSort(std::vectorint arr) {int n arr.size();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;}
}4. 希尔排序Shell Sort
原理是插入排序的一种改进通过将数组分割成若干子序列分别进行插入排序从而加快排序速度。
时间复杂度O(n log n) ~ O(n^2)
代码示例
void shellSort(std::vectorint arr) {int n arr.size();for (int gap n / 2; gap 0; gap / 2) {for (int i gap; i n; i) {int temp arr[i];int j;for (j i; j gap arr[j - gap] temp; j - gap) {arr[j] arr[j - gap];}arr[j] temp;}}
}5. 归并排序Merge Sort
原理采用分治法将数组分成两部分分别排序然后合并排序结果。
时间复杂度O(n log n)
代码示例
void merge(std::vectorint arr, int l, int m, int r) {int n1 m - l 1;int n2 r - m;std::vectorint L(n1), R(n2);for (int i 0; i n1; i) {L[i] arr[l i];}for (int j 0; j n2; j) {R[j] arr[m 1 j];}int i 0, j 0, k l;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(std::vectorint arr, int l, int r) {if (l r) {int m l (r - l) / 2;mergeSort(arr, l, m);mergeSort(arr, m 1, r);merge(arr, l, m, r);}
}6. 快速排序Quick Sort
原理选择一个基准元素通过一趟排序将待排序数组分成两部分其中一部分比基准元素小另一部分比基准元素大然后递归地对这两部分分别进行快速排序。
时间复杂度平均O(n log n)最坏O(n^2)
代码示例
int partition(std::vectorint arr, int low, int high) {int pivot arr[high];int i (low - 1);for (int j low; j high - 1; j) {if (arr[j] pivot) {std::swap(arr[i], arr[j]);}}std::swap(arr[i 1], arr[high]);return (i 1);
}void quickSort(std::vectorint arr, int low, int high) {if (low high) {int pi partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi 1, high);}
}7. 堆排序Heap Sort
原理利用堆这种数据结构来排序。最大堆用于升序排序最小堆用于降序排序。
时间复杂度O(n log n)
代码示例
void heapify(std::vectorint arr, int n, int i) {int largest i;int left 2 * i 1;int right 2 * i 2;if (left n arr[left] arr[largest]) {largest left;}if (right n arr[right] arr[largest]) {largest right;}if (largest ! i) {std::swap(arr[i], arr[largest]);heapify(arr, n, largest);}
}void heapSort(std::vectorint arr) {int n arr.size();for (int i n / 2 - 1; i 0; --i) {heapify(arr, n, i);}for (int i n - 1; i 0; --i) {std::swap(arr[0], arr[i]);heapify(arr, i, 0);}
}8. 计数排序Counting Sort
原理适用于元素范围较小的数组利用数组下标进行排序。
时间复杂度O(n k)其中k是最大值和最小值的范围
代码示例
void countingSort(std::vectorint arr) {int max *std::max_element(arr.begin(), arr.end());int min *std::min_element(arr.begin(), arr.end());int range max - min 1;std::vectorint count(range), output(arr.size());for (int i 0; i arr.size(); i) {count[arr[i] - min];}for (int i 1; i count.size(); i) {count[i] count[i - 1];}for (int i arr.size() - 1; i 0; --i) {output[count[arr[i] - min] - 1] arr[i];count[arr[i] - min]--;}for (int i 0; i arr.size(); i) {arr[i] output[i];}
}总结
这些排序算法各有优劣选择合适的排序算法需要根据数据规模和具体场景来决定。一般来说快速排序和归并排序适用于大多数情况而像计数排序则适用于特定条件下的排序。
