排序算法的实现（归并，快排，堆排，希尔排序 O(N*log(N))）
2024-10-19 04:32:21
今天跟着左老师的视频，理解了四种复杂度为 O(N*log(N))的排序算法，以前也理解过过程，今天根据实际的代码，感觉基本的算法还是很简单的，只是自己写的时候可能一些边界条件，循环控制条件把握不好。
//对于一个int数组，请编写一个选择冒泡算法，对数组元素排序。
//给定一个int数组A及数组的大小n，请返回排序后的数组。
//测试样例：
//[1, 2, 3, 5, 2, 3], 6
//[1, 2, 2, 3, 3, 5] #include <iostream>
using namespace std;
#include<string> void printResult(string str,int* A,int n)
{
cout << str << "的结果:\n";
for (int i = ; i < n; i++)
{
cout << A[i] <<" ";
}
cout << endl;
}
void swap(int *a, int *b)
{
int temp=*a;
*a = *b;
*b = temp;
} //冒泡排序 O(n^2)
class BubbleSort {
public:
int* bubbleSort(int* A, int n) {
// write code here
for (int i = ; i<n; i++)
{
for (int j = ; j<n - i - ; j++)
{
if (A[j]>A[j + ])
{
int temp = A[j];
A[j] = A[j + ];
A[j + ] = temp;
}
}
}
return A;
}
}; //请编写一个选择排序算法 O(n^2)
class SelectionSort {
public:
int* selectionSort(int* A, int n) {
// write code here
int k = ;
for (int i = ; i < n-; i++)
{
k = i;
for (int j = i; j < n; j++)
{
if (A[k]>A[j])
{
k = j;
}
}
if (k!=i)
{
int temp = A[i];
A[i] = A[k];
A[k] = temp;
}
}
return A;
}
}; //请编写一个插入算法 O(n^2)
class InsertionSort
{
public:
int* insertionSort(int* A, int n)
{
for (int i = ; i < n; i++)
{
int temp = A[i];
int j = i - ;
for (; j >= ;j--) //j前面的已经排好序，从后面往前比较，当没有比当前值大的时候bereak;
{
if (A[j]>temp)
{
A[j + ] = A[j];
}
else
{
break;
}
}
A[j + ] = temp;
}
return A;
}
}; //归并排序 O(N*log(N))
class MergeSort {
public:
int* mergeSort(int* A, int n) {
// write code here
mergeSort(A, , n - );
return A;
}
void mergeSort(int* A, int beg, int end)
{
if (beg < end)
{
int mid = beg + (end - beg) / ;
mergeSort(A, beg, mid);
mergeSort(A, mid + , end);
merge(A,beg,mid,end);
}
return;
}
void merge(int* A, int beg_, int mid_, int end_)
{
int *B = new int[end_ - beg_ + ];
int index1 = beg_;
int index2 = mid_ + ;
int i = ;
while (index1<=mid_&&index2<=end_)
{
if (A[index1]<=A[index2])
{
B[i++] = A[index1++];
}
else
{
B[i++] = A[index2++];
}
}
while (index1 <= mid_)
{
B[i++] = A[index1++];
}
while (index2<=end_)
{
B[i++] = A[index2++];
}
//memcpy(A,B,end_-beg_+1);
for (int i = ; i < end_ - beg_ + ;i++)
{
A[beg_+i] = B[i]; //A[beg_++] 不能写，改变了输入参数
}
delete[] B;
}
}; //快速排序 O(N*log(N))
#include <math.h>
class QuickSort {
public:
int* quickSort(int* A, int n) {
// write code here
quickSort(A, , n - );
return A;
}
void quickSort(int* A, int low, int high)
{
if (low <= high)
{
int part = partition(A, low, high);
quickSort(A, low, part - );
quickSort(A, part + , high);
}
return;
} int partition(int* A, int low, int high)
{
int privotKey = A[low]; //基准元素
while (low < high)
{ //从表的两端交替地向中间扫描
while (low < high && A[high] >= privotKey)
--high; //从high 所指位置向前搜索，至多到low+1 位置。将比基准元素小的交换到低端
swap(&A[low], &A[high]);
while (low < high && A[low] <= privotKey)
++low;
swap(&A[low], &A[high]);
}
return low;
}
};
class QuickSort2 {
public:
int* quickSort(int* A, int n) {
// write code here
quickSort(A, , n - );
return A;
}
void quickSort(int* A, int low, int high)
{
if (low <= high)
{
int randn = low + rand() % (high - low + ); //随机选择关键字的下标
swap(&A[randn], &A[high]); //void swap(int* A,int index1,int index2) //最好都操作下标 int part = partition(A, low, high);
quickSort(A, low, part - );
quickSort(A, part + , high);
}
return;
} int partition(int* A, int low, int high) //O(N)
{
//int pivot = A[low];//很多随机选择放在这里面，而且是以值的形式确定，而非下标标记为关键字 int pivot = low-; //关键字的位置
for (int i = low ; i <= high; i++)
{
if (A[i] <= A[high])
{
swap(&A[i], &A[++pivot]); //感觉这样会把A数组前面的值覆盖？-->其实没有交换的效果就是把前面的交换到后面
}
}
return pivot;
}
}; //推排序 O(N*log(N))
class HeapSort {
public:
int* heapSort(int* A, int n) {
// write code here
buildHeap(A, n); //初始时构建堆
//从最后一个元素开始对序列进行调整
for (int i = n - ; i >= ;i--)
{
swap(&A[], &A[i]);
heapAdjust(A,,i);
}
return A;
} void buildHeap(int* A, int size_A)
{
for (int i = (size_A)/ -; i >= ; i--)
{
heapAdjust(A,i,size_A);
}
} void heapAdjust(int* A, int root, int size_A) //大顶堆
{
int leftchild = * root + ;
if (leftchild<size_A) //递归形式
{
int rightchild = leftchild + ;
if (rightchild<size_A)
{
if (A[leftchild]<A[rightchild])
{
leftchild = rightchild;
}
}
//leftchild为左右子节点中较大的结点
if (A[root]<A[leftchild])
{
int temp = A[root];
A[root] = A[leftchild]; //将较大结点值上移到根节点
A[leftchild] = temp; //完成交换，子节点变为以前的根节点
heapAdjust(A, leftchild, size_A);
}
}
return;
}
};
class HeapSort2 {
public:
int* heapSort(int* A, int n) {
// write code here
buildHeap(A, n); //初始时构建堆
//从最后一个元素开始对序列进行调整
for (int i = n - ; i >= ; i--)
{
swap(&A[], &A[i]);
heapAdjust(A, , i);
}
return A;
} void buildHeap(int* A, int size_A)
{
for (int i = (size_A - ) / ; i >= ; i--)
{
heapAdjust(A, i, size_A);
}
} void heapAdjust(int* A, int root, int size_A) //调整为大顶堆
{
int temp = A[root];
int leftchild = * root + ;
while (leftchild < size_A) //非递归形式
{
int rightchild = leftchild + ;
if (rightchild < size_A)
{
if (A[leftchild] < A[rightchild])
{
leftchild = rightchild;
}
}
//leftchild为左右子节点中较大的结点
if (A[root] < A[leftchild])
{
A[root] = A[leftchild]; //将较大结点值上移到根节点
root = leftchild; //更新新的根节点
leftchild = * root + ;
}
else //当前结点大于左右子节点则不需要调整
{
break;
}
A[root] = temp; //完成交换，子节点变为以前的根节点
}
return;
}
}; //希尔排序 O(N*log(N)) ---不稳定
class ShellSort {
public:
int* shellSort(int* A, int n) {
// write code here
int dk = n / ;
while (dk>=)
{
shellSort2(A,n,dk);
dk /= ;
}
return A;
}
void shellSort(int* A, int n, int dk)
{
for (int i = dk; i < n;i++)
{
int index = i; //当前访问的位置
while (index>=dk)
{
if (A[index-dk]>A[index])
{
swap(&A[index-dk],&A[index]); //交换不算最优，找到插入位置才交换
index -= dk;
}
else
{
break;
}
}
}
}
void shellSort2(int* A,int n,int dk)
{
for (int i = dk; i < n;i++)
{
if (A[i]<A[i-dk]) //找到插入位置
{
int x = A[i];//复制哨兵
A[i] = A[i - dk];
int j = i - dk; //从该位置向前查找
while (x<A[j]&&j>=) //防止j越界
{
A[j] = A[j - dk];
j -= dk; //向前移动
}
A[j + dk] = x;// 插入到正确位置
}
}
} }; #define N 13
int main()
{
//待排数据输入方式：
/*int N = 0;
cout << "排序数据个数：\n";
cin >> N;
int* A = new int[N];
cout << "请输入待排序的数据：\n";
for (int i = 0; i < N; i++)
{
cin >> A[i];
}*/
//数据直接给定
int B[N] = { , , , , , };
int C[] = { , , , , , , , , , , , , };
int* A = C; //从文件中读取，大量数据，计算时间复杂度 printResult("待排原始数据：", C, N); BubbleSort bubble;
bubble.bubbleSort(A,N);
printResult("bubbleSort", A, N); SelectionSort select;
select.selectionSort(A, N);
printResult("selectSort", A, N); InsertionSort insert;
insert.insertionSort(A, N);
printResult("InsetSort", A, N); MergeSort merge;
merge.mergeSort(A, N);
printResult("MergeSort", A, N); QuickSort qucik;
qucik.quickSort(A, N);
printResult("QucikSort",A,N); QuickSort2 qucik2;
qucik2.quickSort(A, N);
printResult("QucikSort2", A, N); HeapSort heap;
heap.heapSort(A, N);
printResult("heapSort", A, N); HeapSort2 heap2;
heap2.heapSort(A, N);
printResult("heapSort2", A, N); ShellSort shell;
shell.shellSort(A,N);
printResult("shellSort", A, N); return ;
}
最新文章
- C# 可空值类型
- 转自文翼的博客：将本地时间转换为 GMT 时间
- WEB界面onload前的加载流程❤❤
- C#之读取web上的xml
- Linux环境安装Jenkins
- PHP和.NET通用的加密解密函数类,均使用3DES加解密 .
- Request.QueryString
- Text Kit入门
- Mac通过以太网共享网络
- POJ2002 Squares(枚举)
- Vue.js快速入门
- hdu1695(莫比乌斯)或欧拉函数+容斥
- Spring之SpringMVC(源码)启动初始化过程分析
- Linux下的编程实战【转】
- 04(1) 基于上下文相关的GMM-HMM声学模型1
- XOR算法的原理和实现
- nodejs爬虫初试---superagent和cheerio
- 插件前奏-android黑科技 hook介绍
- python标准库之random模块
- PAT 1058 A+B in Hogwarts