C++内部排序算法全解析：代码实现与性能对比

八大内部排序算法实战解析

排序是计算机科学中最基础的操作之一。为了在 C++ 环境下高效处理数据，理解并掌握各类内部排序算法至关重要。以下将分类介绍常用的内部排序方法，并提供可直接运行的 C++ 实现代码。

第一类：插入排序

插入排序的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。它主要包括直接插入、折半插入和希尔排序三种形式。

第1步：直接插入排序 (InsertSort)

原理：将数组分为已排序和未排序两部分，依次将未排序元素插入到已排序部分的正确位置。

• 时间复杂度：最好 $O(n)$，最坏 $O(n^2)$，平均 $O(n^2)$。
• 空间复杂度：$O(1)$。
• 稳定性：稳定。

void InsertSort(ElementType A[], int n)
{
 int i,j;
 ElementType temp; 
 for(i=1; i<n; ++i)
 {
 temp = A[i]; 
 for(j = i; j>0 && A[j-1]>temp; --j)
 A[j] = A[j-1];
 A[j] = temp;
 }
}

第2步：折半插入排序 (BinaryInsertSort)

原理：在直接插入排序基础上，利用二分查找法确定插入位置，减少比较次数，但移动次数不变。

• 时间复杂度：$O(n^2)$。
• 空间复杂度：$O(1)$。
• 稳定性：稳定。

void BinaryInsertSort(ElementType A[], int n)
{
 int i, j, low, high, mid;
 ElementType temp;
 for(i=1; i<n; ++i)
 {
 temp = A[i];
 low = 0; high = i-1; 
 while(low <= high)
 {
 mid = (low+high)/2; 
 if(A[mid] > temp) high = mid-1;
 else low = mid+1;
 }
 for(j=i-1; j>=high+1; --j) A[j+1] = A[j];
 A[high+1] = temp;
 }
}

第3步：希尔排序 (ShellSort)

原理：又称缩小增量排序，先将整个待排记录序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

• 时间复杂度：依赖于增量序列，通常优于 $O(n^2)$。
• 空间复杂度：$O(1)$。
• 稳定性：不稳定。

void ShellSort(ElementType A[], int n)
{
 int i, j, dk; 
 for(dk=n/2; dk>0; dk/=2)
 {
 for(i=dk; i<n; ++i)
 {
 temp = A[i];
 for(j=i-dk; j>=0 && A[j]>temp; j-=dk)
 A[j+dk] = A[j];
 A[j+dk] = temp;
 }
 }
}

第二类：交换排序

交换排序主要通过比较两个元素的大小来交换它们在序列中的位置，主要包括冒泡排序和快速排序。

第4步：冒泡排序 (BubbleSort)

原理：重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序错误就把他们交换过来。

• 时间复杂度：最好 $O(n)$，最坏 $O(n^2)$。
• 空间复杂度：$O(1)$。
• 稳定性：稳定。

void BubbleSort(ElementType A[], int n)
{
 for(int i=0; i<n-1; ++i)
 {
 bool flag = false;
 for(int j=n-1; j>i; --j)
 {
 if(A[j-1] > A[j]) 
 {
 flag = true;
 A[j-1] = A[j-1]^A[j];
 A[j] = A[j-1]^A[j];
 A[j-1] = A[j-1]^A[j];
 }
 }
 if(flag == false) return;
 }
}

第5步：快速排序 (QuickSort)

原理：采用分治法策略。选择一个基准元素，将序列分成两部分，左边小于基准，右边大于基准，然后递归地对两部分进行排序。

• 时间复杂度：平均 $O(n \log n)$，最坏 $O(n^2)$。
• 空间复杂度：$O(\log n)$ (递归栈)。
• 稳定性：不稳定。

int Partition(ElementType A[], int low, int high)
{
 ElementType pivot = A[low];
 while(low < high)
 {
 while(low<high && A[high]>=pivot) --high;
 A[low] = A[high];
 while(low<high && A[low]<=pivot) ++low;
 A[high] = A[low];
 }
 A[low] = pivot;
 return low;
}

void QuickSort(ElementType A[], int low, int high)
{
 if(low < high) 
 {
 int pivotPos = Partition(A, low, high);
 QuickSort(A, low, pivotPos-1);
 QuickSort(A, pivotPos+1, high);
 }
}

第三类：选择排序

选择排序每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子序列最后，直到全部记录排序完毕。

第6步：简单选择排序 (SelectedSort)

原理：在未排序序列中找到最小元素，存放到排序序列的起始位置，然后从剩余未排序元素中继续寻找最小元素，以此类推。

• 时间复杂度：$O(n^2)$。
• 空间复杂度：$O(1)$。
• 稳定性：不稳定。

void SelectedSort(ElementType A[], int n)
{
 for(int i=0; i<n-1; ++i)
 {
 int minPos = i; 
 for(int j=i+1; j<n; ++j)
 if(A[j] < A[minPos]) minPos = j;
 if(minPos != i)
 {
 A[i] = A[i]^A[minPos];
 A[minPos] = A[i]^A[minPos];
 A[i] = A[i]^A[minPos];
 }
 }
}

第7步：堆排序 (HeapSort)

原理：利用大根堆或小根堆的特性。首先将数组建成大根堆，此时堆顶元素最大，将其与末尾元素交换，然后重新调整堆，重复此过程。

• 时间复杂度：$O(n \log n)$。
• 空间复杂度：$O(1)$。
• 稳定性：不稳定。

void AdjustDown(ElementType A[], int i, int len)
{
 ElementType temp = A[i];
 for(int largest=2*i+1; largest<len; largest=2*largest+1)
 {
 if(largest!=len-1 && A[largest+1]>A[largest]) ++largest;
 if(temp < A[largest]) {
 A[i] = A[largest]; i = largest;
 } else break;
 }
 A[i] = temp;
}

void HeapSort(ElementType A[], int n)
{
 BuildMaxHeap(A, n); // 假设BuildMaxHeap已定义
 for(int i=n-1; i>0; --i) 
 {
 A[0] = A[0]^A[i]; A[i] = A[0]^A[i]; A[0] = A[0]^A[i];
 AdjustDown(A, 0, i); 
 }
}

第四类：归并排序

第8步：2-路归并排序 (MergeSort)

原理：将两个或两个以上的有序表合并成一个新的有序表。通常采用分治法，将数组递归拆分至单个元素，然后两两归并。

• 时间复杂度：$O(n \log n)$。
• 空间复杂度：$O(n)$。
• 稳定性：稳定。

ElementType *B = new ElementType[13]; // 辅助数组
void Merge(ElementType A[], int low, int mid, int high)
{
 int i, j, k;
 for(k=low; k<=high; ++k) B[k] = A[k];
 for(i=low,j=mid+1,k=i; i<=mid&&j<=high; ++k)
 {
 if(B[i] <= B[j]) A[k] = B[i++];
 else A[k] = B[j++];
 }
 while(i<=mid) A[k++] = B[i++];
 while(j<=high) A[k++] = B[j++];
}

void MergeSort(ElementType A[], int low, int high)
{
 if(low < high)
 {
 int mid = (low + high)/2;
 MergeSort(A, low, mid);
 MergeSort(A, mid+1, high);
 Merge(A, low, mid, high);
 }
}

测试与验证

为了验证上述算法的正确性，可以使用统一的测试数据进行调用。以下是一个简单的 `main` 函数示例，用于初始化数据和打印结果：

void print(ElementType A[], int n)
{
 for(int i=0; i<n; ++i) cout << A[i] << " ";
 cout << endl;
}

int main()
{
 ElementType Arr[13] = {5,2,1,8,3,6,4,7,0,9,12,10,11};
 // 取消注释以运行特定排序算法
 // InsertSort(Arr, 13);
 // QuickSort(Arr, 0, 12);
 // ...
 print(Arr, 13);
 return 0;
}

总结

不同的排序算法适用于不同的场景。对于小规模数据，插入排序因其简洁和低常数因子往往是不错的选择；而对于大规模数据，快速排序和堆排序通常效率更高。需要注意的是，快排在最坏情况下性能会退化，而堆排序虽然速度稳定但不稳定且常数较大。在实际开发中，应结合数据规模、内存限制及对稳定性的要求选择合适的算法。

以上就是基于C++实现的各种内部排序算法的详细内容，更多关于C++算法优化的资料请关注本站其它相关文章！