站长工具国色天香,绿色农产品网站,设计师培训心得,忻州建站公司介绍
排序算法是计算机科学中的一类算法#xff0c;用于对元素序列进行排序#xff0c;以便按照某种特定的顺序#xff08;如升序或降序#xff09;组织数据。这些算法在软件开发和数据处理中扮演着至关重要的角色#xff0c;因为它们可以提高搜索效率、优化数据结构的访…介绍
排序算法是计算机科学中的一类算法用于对元素序列进行排序以便按照某种特定的顺序如升序或降序组织数据。这些算法在软件开发和数据处理中扮演着至关重要的角色因为它们可以提高搜索效率、优化数据结构的访问和处理等。
常见的排序算法有
类型时间复杂度空间复杂度冒泡排序Bubble SortO(n^2)其中n是数列的长度O(1)选择排序Selection SortO(n^2)O(1)插入排序Insertion SortO(n^2)O(1)归并排序Merge SortO(n log n)O(n)快速排序Quick Sort平均O(n log n)最坏O(n^2)O(log n)堆排序Heap SortO(n log n)O(1)希尔排序Shell Sort取决于间隔序列的选择最好可以达到O(n log^2 n)O(1)计数排序Counting SortO(n k)O(k)桶排序Bucket SortO(n k)O(n k)基数排序Radix Sort时间复杂度O(nk)O(n k)
此外还有鸡尾酒排序Cocktail Sort双向冒泡排序、图书馆排序Library SortCocktail Sort的变种、鸽巢排序Pigeonhole Sort、啤酒排序Beer Sort、循环排序Cyclic Sort、位排序Bitonic Sort、梳排序Comb Sort、TimSort一种混合排序算法Python的内置排序算法之一、Bogo Sort一种通过随机打乱输入数据来排序的非常低效算法、Stooge Sort通过递归地将数组分成三部分来排序的算法、Panama Sort通过移除数组中最小或最大的元素来排序的算法、Cocktail Shaker Sort双向选择排序、Tree Sort利用二叉搜索树进行排序的算法、Cycle Sort通过循环交换来排序的算法、Gnome Sort通过比较和移动来排序的算法类似于插入排序等等。
冒泡排序Bubble Sort
冒泡排序Bubble Sort是一种简单的排序算法它的原理基于重复遍历待排序的数列通过比较相邻的元素并在必要时交换它们的位置来实现排序。冒泡排序的基本思想是在每次遍历过程中将最大的元素“冒泡”到数列的末尾这个过程类似于气泡从水底升到水面。以下是
冒泡排序的详细步骤 比较相邻元素从数列的开始位置比较第一个和第二个元素如果第一个元素大于第二个元素升序排序的情况则交换它们的位置。继续比较第二个和第三个元素以此类推直到到达数列的末尾。 冒泡至末尾在第一次遍历结束时最大的元素会被放置在数列的最后一个位置。接下来的遍历将忽略这个已经排序好的元素因为它已经在正确的位置上了。 重复过程重复上述比较和交换的过程但每次遍历时都减少一个元素的比较因为最后一个元素已经是最大的不需要再比较这样进行直到整个数列都被排序。 优化在某些情况下可以对冒泡排序进行优化。例如如果在一次遍历中没有发生任何交换这意味着数列已经是有序的因此可以提前结束排序过程。
c冒泡排序示例
#include iostream
using namespace std;// 交换两个元素的值
void swap(int a, int b) {int temp a;a b;b temp;
}// 冒泡排序函数
void bubbleSort(int arr[], int n) {bool swapped;// 外层循环控制遍历次数for (int i 0; i n - 1; i) {swapped false; // 标记变量用于优化冒泡排序// 内层循环负责进行相邻元素的比较和交换for (int j 0; j n - i - 1; j) {if (arr[j] arr[j 1]) {swap(arr[j], arr[j 1]);swapped true; // 发生交换标记为true}}// 如果在这一轮遍历中没有发生交换说明数组已经有序可以提前结束排序if (!swapped) {break;}}
}// 打印数组的函数
void printArray(int arr[], int size) {for (int i 0; i size; i) {cout arr[i] ;}cout endl;
}// 主函数
int main() {int arr[] {64, 34, 25, 12, 22, 11, 90};int n sizeof(arr) / sizeof(arr[0]);cout 原始数组: ;printArray(arr, n);bubbleSort(arr, n);cout 排序后的数组: ;printArray(arr, n);return 0;
}这段代码首先定义了一个swap函数用于交换两个整数的值。bubbleSort函数实现了冒泡排序算法它接受一个整数数组和数组的长度作为参数。在排序过程中使用了一个布尔变量swapped来检查内层循环中是否发生了元素交换如果在某次遍历中没有发生交换说明数组已经排序完成可以提前退出循环。
printArray函数用于打印数组中的元素。在main函数中定义了一个待排序的数组并调用bubbleSort函数进行排序然后打印排序前后的数组。
选择排序Selection Sort
选择排序Selection Sort是一种简单直观的排序算法。它的工作原理是每次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完。选择排序主要有两种实现方式直接选择排序和树状选择排序。
以下是选择排序的基本步骤
寻找最小元素在未排序序列中找到最小或最大元素存放到排序序列的起始位置。重复寻找再从剩余未排序元素中继续寻找最小或最大元素然后放到已排序序列的末尾。
选择排序c示例
#include iostream
using namespace std;// 选择排序函数
void selectionSort(int arr[], int n) {int i, j, minIndex, temp;// 外层循环控制遍历次数for (i 0; i n - 1; i) {// 找到从i到n-1中最小元素的索引minIndex i;for (j i 1; j n; j) {if (arr[j] arr[minIndex]) {minIndex j;}}// 将找到的最小元素与第i位置的元素交换if (minIndex ! i) {temp arr[i];arr[i] arr[minIndex];arr[minIndex] temp;}}
}// 打印数组的函数
void printArray(int arr[], int size) {for (int i 0; i size; i) {cout arr[i] ;}cout endl;
}// 主函数
int main() {int arr[] {64, 34, 25, 12, 22, 11, 90};int n sizeof(arr) / sizeof(arr[0]);cout 原始数组: ;printArray(arr, n);selectionSort(arr, n);cout 排序后的数组: ;printArray(arr, n);return 0;
}在这个示例中selectionSort函数实现了选择排序算法。它首先在未排序的序列中找到最小元素的索引然后将其与序列中当前位置的元素交换。这个过程会一直重复直到整个数组被排序。
插入排序Insertion Sort
插入排序Insertion Sort是一种简单直观的排序算法它的工作原理是将数组分为已排序部分和未排序部分然后逐个将未排序部分的元素插入到已排序部分的适当位置。插入排序在实际应用中非常高效尤其是对于小型数据集或基本有序的数据集。
以下是插入排序的基本步骤 构建有序序列将数组的第一个元素视为已排序部分其余元素视为未排序部分。 扫描未排序部分从数组的第二个元素开始扫描未排序部分的每个元素。 插入元素将当前元素与已排序部分的元素从后往前比较找到合适的位置插入当前元素保持已排序部分的有序性。 重复过程重复步骤2和3直到所有元素都被插入到已排序部分完成排序。
插入排序c示例
#include iostream
using namespace std;// 插入排序函数
void insertionSort(int arr[], int n) {int i, key, j;// 从第二个元素开始进行插入排序for (i 1; i n; i) {key arr[i]; // 当前需要插入的元素j i - 1;// 将大于key的元素向后移动一位while (j 0 arr[j] key) {arr[j 1] arr[j];j j - 1;}// 插入key到正确的位置arr[j 1] key;}
}// 打印数组的函数
void printArray(int arr[], int size) {for (int i 0; i size; i) {cout arr[i] ;}cout endl;
}// 主函数
int main() {int arr[] {12, 11, 13, 5, 6};int n sizeof(arr) / sizeof(arr[0]);cout 原始数组: ;printArray(arr, n);insertionSort(arr, n);cout 排序后的数组: ;printArray(arr, n);return 0;
}在这个示例中insertionSort函数实现了插入排序算法。它从数组的第二个元素开始将每个元素与已排序部分的元素进行比较并找到合适的位置插入。这个过程一直重复直到整个数组都被排序。
归并排序Merge Sort
归并排序Merge Sort是一种分治算法它通过递归地将数组分成两半然后对这两半分别进行排序最后将排序好的两半合并成一个有序的数组。归并排序的核心在于合并两个有序数组的过程这个过程是稳定的即相同元素在合并后保持原来的相对顺序。
以下是归并排序的基本步骤 分解将数组递归地分成两半直到每个子数组只包含一个元素。由于每个元素本身可以视为一个有序数组所以当子数组的大小为1时递归结束。 合并将两个有序的子数组合并成一个更大的有序数组。合并过程是逐个比较两个子数组的元素将较小的元素放入新的数组中直到所有元素都被合并。 递归合并重复合并过程直到整个数组被合并成一个有序的数组。
归并排序c示例
#include iostream
using namespace std;// 合并两个有序数组的函数
void merge(int arr[], int left, int mid, int right) {int n1 mid - left 1; // 左半部分的大小int n2 right - mid; // 右半部分的大小// 创建临时数组int L[n1], R[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, j 0, 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;}
}// 归并排序函数
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);}
}// 打印数组的函数
void printArray(int arr[], int size) {for (int i 0; i size; i) {cout arr[i] ;}cout endl;
}// 主函数
int main() {int arr[] {12, 11, 13, 5, 6};int n sizeof(arr) / sizeof(arr[0]);cout 原始数组: ;printArray(arr, n);mergeSort(arr, 0, n - 1);cout 排序后的数组: ;printArray(arr, n);return 0;
}在这个示例中mergeSort函数实现了归并排序算法。它首先找到数组的中间位置递归地对左右两半进行排序然后调用merge函数将排序好的两半合并成一个有序数组。
快速排序Quick Sort
快速排序Quick Sort是一种高效的排序算法采用分治法Divide and Conquer的策略来把一个序列分为较小和较大的两个子序列然后递归地排序两个子序列。快速排序的关键在于选择一个元素作为“基准”pivot并围绕这个基准进行分区partition操作使得小于基准的元素都在其左侧大于基准的元素都在其右侧。
以下是快速排序的基本步骤 选择基准从数组中选择一个元素作为基准。选择方式有多种如选择第一个元素、最后一个元素、中间元素或随机一个元素。 分区操作重新排列数组所有比基准值小的元素摆放在基准前面所有比基准值大的元素摆在基准的后面相等的数可以到任一边。在这个分区退出之后该基准就处于数组的中间位置。这个称为分区partition操作。 递归排序递归地将小于基准值元素的子数组和大于基准值元素的子数组排序。
快速排序c示例
#include iostream
using namespace std;// 交换两个元素的值
void swap(int a, int b) {int t a;a b;b t;
}// 分区函数选择左端点作为基准
int partition(int arr[], int low, int high) {int pivot arr[low]; // 选择基准int i low 1;int j high;while (true) {// 找到比基准大的元素while (i j arr[i] pivot) {i;}// 找到比基准小的元素while (i j arr[j] pivot) {j--;}if (i j) {break;}// 交换两个元素的位置swap(arr[i], arr[j]);}// 将基准元素放到正确的位置swap(arr[low], arr[j]);return j;
}// 快速排序函数
void quickSort(int arr[], int low, int high) {if (low high) {// pi是分区索引arr[pi]现在在正确的位置int pi partition(arr, low, high);// 分别递归地对基准前后的子数组进行快速排序quickSort(arr, low, pi - 1);quickSort(arr, pi 1, high);}
}// 打印数组的函数
void printArray(int arr[], int size) {for (int i 0; i size; i) {cout arr[i] ;}cout endl;
}// 主函数
int main() {int arr[] {10, 7, 8, 9, 1, 5};int n sizeof(arr) / sizeof(arr[0]);cout 原始数组: ;printArray(arr, n);quickSort(arr, 0, n - 1);cout 排序后的数组: ;printArray(arr, n);return 0;
}在这个示例中quickSort函数实现了快速排序算法。它首先调用partition函数来选择基准并进行分区操作然后递归地对基准前后的子数组进行快速排序。
堆排序Heap Sort
堆排序Heap Sort是一种基于比较的排序算法它使用二叉堆特殊的完全二叉树的数据结构来对元素进行排序。堆排序的特点是无论升序还是降序排序都可以在O(n log n)的时间复杂度内完成。堆排序的工作原理可以分为两个主要步骤建立堆和堆排序。
以下是堆排序的基本步骤 建立堆将无序的输入数组构造成一个最大堆或最小堆取决于排序的类型。最大堆的性质是每个节点的值都大于或等于其子节点的值而最小堆则相反。 堆排序将堆顶元素最大或最小元素与堆的最后一个元素交换这样最大或最小元素就放置到了数组的末尾。减少堆的大小排除已经排序好的最后一个元素并对新的堆顶元素进行“堆化”heapify以恢复堆的性质。 重复上述过程直到堆的大小减少到1这时数组已经完全排序。
堆排序c示例
#include iostream
using namespace std;void buildMaxHeap(int arr[], int n) {// 从最后一个非叶子节点开始向上调整每个节点for (int i n / 2 - 1; i 0; i--) {heapifyMax(arr, n, i);}
}void heapifyMax(int 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) {swap(arr[i], arr[largest]);heapifyMax(arr, n, largest);}
}void heapSort(int arr[], int n) {buildMaxHeap(arr, n); // 建立最大堆for (int i n - 1; i 0; i--) {// 将当前最大元素与末尾元素交换swap(arr[0], arr[i]);// 堆的大小减少1调整剩余的堆heapifyMax(arr, i, 0);}
}void printArray(int arr[], int n) {for (int i 0; i n; i) {cout arr[i] ;}cout endl;
}int main() {int arr[] {12, 11, 13, 5, 6};int n sizeof(arr) / sizeof(arr[0]);cout 原始数组: ;printArray(arr, n);heapSort(arr, n);cout 排序后的数组: ;printArray(arr, n);return 0;
}在这个示例中heapSort函数实现了堆排序算法。首先调用buildMaxHeap函数建立最大堆然后通过不断地将堆顶元素与末尾元素交换并调整堆来完成排序。
希尔排序Shell Sort
希尔排序Shell Sort是插入排序的一种改进版本也被称为“缩小增量排序”。它通过引入一个增量gap来允许交换更远距离的元素从而可以快速减少大量的小范围无序情况。希尔排序的核心思想是将相距一定间隔的一组元素进行插入排序随着间隔逐渐减小整个数组趋于有序最后当间隔为1时进行最后一次插入排序此时数组已经基本有序所以需要的移动次数会很少。
以下是希尔排序的基本步骤
选择增量序列增量序列的选择对希尔排序的性能有很大影响。常见的增量序列有希尔原始序列N/2N/4…1Hibbard增量序列1, 3, 7, …, 2^k - 1Knuth序列1, 4, 13, …, (3^k - 1)/2等。
分组插入排序按照当前增量将数组分为若干子序列对每个子序列进行插入排序。
减小增量重复排序减小增量值并重复上述排序过程直到增量为1进行最后一次插入排序。
完成排序当增量减至1时整个数组将进行一次标准的插入排序此时数组已经基本有序所以排序会很快完成。
希尔排序c示例
#include iostream
using namespace std;// 插入排序的辅助函数
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;}
}// 希尔排序函数
void shellSort(int arr[], int n) {for (int gap n / 2; gap 0; gap / 2) {// 从第gap个元素开始逐个对其所在组进行直接插入排序for (int i gap; i n; i) {insertionSort(arr, 1); // 这里只对一个元素进行插入排序}}
}// 打印数组的函数
void printArray(int arr[], int size) {for (int i 0; i size; i) {cout arr[i] ;}cout endl;
}// 主函数
int main() {int arr[] {12, 34, 54, 2, 3};int n sizeof(arr) / sizeof(arr[0]);cout 原始数组: ;printArray(arr, n);shellSort(arr, n);cout 排序后的数组: ;printArray(arr, n);return 0;
}在这个示例中shellSort函数实现了希尔排序算法。它首先计算出每次排序的增量gap然后对每个子序列进行插入排序。随着增量gap的减小数组逐渐变得接近有序最后当gap为1时整个数组将进行一次插入排序完成排序。
