稳定排序算法是指:在排序过程中,相同元素的相对次序不会发生改变的排序算法。它保证了序列中相同元素的顺序不变,适用于对数据中相对顺序很重要的排序问题。以下是介绍一些常见的稳定排序算法。
冒泡排序(Bubble Sort)
冒泡排序是一种简单的排列算法。它重复地遍历待排序的序列,比较相邻的元素大小,如果顺序错误就将它们交换,直到没有需要交换的元素为止。
冒泡排序的效率较低,时间复杂度为 O(n^2),但由于其实现简单,代码易于理解,所以在某些场景下仍然会被使用。
示例:
// 定义一个冒泡排序函数,用于排序 int 类型数组
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]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
归并排序(Merge Sort)
归并排序是一种分治算法,它将原问题拆分成多个子问题,每个子问题都解决后,将它们合并起来得到原问题的解。
在归并排序中,先将序列拆分成两个子序列,然后对每个子序列进行递归排序。随后,将两个有序的子序列合并成一个有序的序列。
归并排序的时间复杂度为 O(nlogn),具有较好的性能表现。同时,归并排序也具有可扩展性,支持并行化处理,因此在多线程等需求较高的场景下比较常用。
示例:
// 定义一个归并排序函数,用于排序 int 类型数组
void mergeSort(int* arr,int left,int right,int* temp)
{
if(left<right)
{
int mid = (left+right)/2;
mergeSort(arr,left,mid,temp);//左递归
mergeSort(arr,mid+1,right,temp);//右递归
merge(arr,left,mid,right,temp);//合并
}
}
void merge(int *arr,int left,int mid,int right,int *temp)
{
int i = left; //左序列指针
int j = mid + 1; //右序列指针
int t = 0; //临时数组指针
while(i <= mid && j <= right)
{
if(arr[i] <= arr[j])
{
temp[t++] = arr[i++];
}
else
{
temp[t++] = arr[j++];
}
}
while(i <= mid) //将左边剩余元素填充进temp中
{
temp[t++] = arr[i++];
}
while(j <= right) //将右序列剩余元素填充进temp中
{
temp[t++] = arr[j++];
}
t = 0; //从临时数组拷贝回原数组
while(left <= right)
{
arr[left++] = temp[t++];
}
}
以上是两种稳定排序算法的实现示例,它们都具有稳定性和可读性等优点。而在实际使用时,我们需要根据具体的需求和数据量选择最适合的排序算法,在时间和空间上做出权衡。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:详解稳定排序算法原理与使用方法 - Python技术站