mysort.h
#ifndef MYSORT_H
#define MYSORT_H
class MySort
{
public:
MySort();
static MySort* getInstance();
//冒泡排序
void BubbleSort(int* arr, int len);
//插入排序
void InsertSort(int* arr, int len);
//希尔排序
void ShellSort(int* arr, int len);
//归并排序
void MergeSort(int* arr, int n);
//快速排序
void QuickSort(int* arr, int low, int high);
//堆排序
void HeapSort(int* arr, int len);
private:
static MySort* m_pInstance;
};
#endif // MYSORT_H
mysort.cpp
#include "mysort.h"
MySort::MySort()
{
}
MySort* MySort::m_pInstance = nullptr;
MySort *MySort::getInstance()
{
if(m_pInstance == nullptr)
{
m_pInstance = new MySort;
}
return m_pInstance;
}
//冒泡排序
//双重循环中比较数组两个元素，顺序错误进行交换
//平均时间复杂度：O(n^2) 最差时间复杂度：O(n^2)
//稳定
void MySort::BubbleSort(int *arr, int len)
{
for(int i = 0; i < len - 1; i++)
{
for(int j = 0; j < len - 1; j++)
{
if(arr[j] > arr[j+1])//相邻元素对比交换
{
int tmp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = tmp;
}
}
}
}
//插入排序
//从第二个位置开始向前比较并挪动到合适的位置上，直到最后一个元素结束为止
//平均时间复杂度：O(n^2) 最差时间复杂度：O(n^2)
//稳定
void MySort::InsertSort(int *arr, int len)
{
int preIndex = 0, current = 0;
for(int i = 1; i < len; i++)
{
preIndex = i - 1;
current = arr[i];
while(preIndex >= 0 && arr[preIndex] > current)
{
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
}
//希尔排序
//比如有8个数字，分为4组，2组，1组，每组进行插入排序
//平均时间复杂度：O 最差时间复杂度：O
//不稳定
//数组首地址，数组长度，分组起始位置，步长
void ShellSort_Group(int arr[], int length, int start, int step)
{
for (int i = start + step; i < length; i += step)
{
int tmp = arr[i];
int j = i - step;
while (j >= start && arr[j] >= tmp)
{
arr[j + step] = arr[j];
j -= step;
}
arr[j + step] = tmp;
}
return;
}
void MySort::ShellSort(int *arr, int len)
{
//step为步长
for (int step = len/2; step > 0; step /= 2)
{
for (int i = 0; i < step; i++)
{
ShellSort_Group(arr, len, i, step);
}
}
}
//归并排序
//把长度为n的输入序列分成两个长度为n/2的子序列,对这两个子序列分别采用归并排序,将两个排序好的子序列合并成一个最终的排序序列
//在“递”的过程中，对数组均等一分为二，再将子数组，一分为二....; 在“归”的过程中，将这两个有序的子数组合并成一个有序的子数组
//归并排序是一种比较占内存，但却效率高且稳定的算法,采用分治法的一个非常典型的应用(效率最高)
//时间复杂度为O(nlogn)
//稳定
void Merge(int *arr, int n)
{
int *temp = new int[n];
int b = 0; // 辅助数组的起始位置
int mid = n / 2; // mid将数组从中间划分，前一半有序，后一半有序
int first = 0, second = mid; // 两个有序序列的起始位置
while (first < mid && second < n)
{
if (arr[first] <= arr[second]) // 比较两个序列
temp[b++] = arr[first++];
else
temp[b++] = arr[second++];
}
while(first < mid) // 将剩余子序列复制到辅助序列中
temp[b++] = arr[first++];
while(second < n)
temp[b++] = arr[second++];
for (int i = 0; i < n; ++i) // 辅助序列复制到原序列
arr[i] = temp[i];
}
void MySort::MergeSort(int *arr, int n)
{
if (n <= 1) // 递归出口
return;
if (n > 1)
{
MergeSort(arr, n / 2); // 对前半部分进行归并排序
MergeSort(arr + n / 2, n - n / 2); // 对后半部分进行归并排序
Merge(arr, n); // 归并两部分
}
}
//快速排序
//设置一个分界值,趟排序过后，左边部分中各个数据元素都小于分界值，而右边部分中各数据元素都大于或等于分界值,重复递归此操作
//快速排序、归并排序的理想时间复杂度都是O(nlogn)，但是快速排序的时间复杂度并不稳定，最坏情况下复杂度为O(n^2)，所以最理想的算法还是归并排序
//快速排序是非常重要且应用比较广泛的一种高效率排序算法
//快速排序的优点在于平均性能好，缺点在于在初始序列有序或者基本有序时，其时间复杂度降为O(n*n)，因此在序列有序或者逆序的情况下最不利于发挥其长处
//不稳定
void MySort::QuickSort(int *arr, int low, int high)
{
if (high <= low)
return;
int i = low;
int j = high;
int key = arr[low];
while (true)
{
while (arr[i] <= key)
{
i++;
if (i == high)
{
break;
}
}
while (arr[j] >= key)
{
j--;
if (j == low)
{
break;
}
}
if (i >= j)
break;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
arr[low] = arr[j];
arr[j] = key;
QuickSort(arr, low, j - 1);
QuickSort(arr, j + 1, high);
}
//堆排序
//升序用大根堆，降序就用小根堆(默认为升序)
//堆排序时间复杂度为O（nlogn）,与归并排序相比，空间上使用少，在空间较少（归并排序不适合），要求实时（快速排序不适合时间限制）的嵌入式系统中非常有用
void HeapAdjust(int* arr, int start, int end)
{
int tmp = arr[start];
for (int i = 2 * start + 1; i <= end; i = i * 2 + 1)
{
if (i < end && arr[i] < arr[i + 1])//有右孩子并且左孩子小于右孩子
{
i++;
}//i一定是左右孩子的最大值
if (arr[i] > tmp)
{
arr[start] = arr[i];
start = i;
}
else
{
break;
}
}
arr[start] = tmp;
}
void MySort::HeapSort(int *arr, int len)
{
//第一次建立大根堆，从后往前依次调整
for(int i=(len-1-1)/2;i>=0;i--)
{
HeapAdjust(arr, i, len - 1);
}
//每次将根和待排序的最后一次交换，然后在调整
int tmp;
for (int i = 0; i < len - 1; i++)
{
tmp = arr[0];
arr[0] = arr[len - 1-i];
arr[len - 1 - i] = tmp;
HeapAdjust(arr, 0, len - 1-i- 1);
}
}
main.cpp
#include
#include "mysort.h"
using namespace std;
int main(int argc, char *argv[])
{
MySort* sortObj = MySort::getInstance();
//冒泡排序
int arr1[] = {57, 68, 59, 52, 72, 28, 96, 33, 24};
sortObj->BubbleSort(arr1, sizeof(arr1) / sizeof(arr1[0]));
cout << "BubbleSort:"<< endl;
for(int i = 0; i < sizeof(arr1) / sizeof(arr1[0]); i++)
{
cout << arr1[i] << " " << endl;
}
//插入排序
int arr2[] = {57, 68, 59, 52, 72, 28, 96, 33, 24};
sortObj->InsertSort(arr2, sizeof(arr2) / sizeof(arr2[0]));
cout << "InsertSort:"<< endl;
for(int i = 0; i < sizeof(arr2) / sizeof(arr2[0]); i++)
{
cout << arr2[i] << " " << endl;
}
//希尔排序
int arr3[] = {57, 68, 59, 52, 72, 28, 96, 33, 24};
sortObj->ShellSort(arr3, sizeof(arr3) / sizeof(arr3[0]));
cout << "ShellSort:"<< endl;
for(int i = 0; i < sizeof(arr3) / sizeof(arr3[0]); i++)
{
cout << arr3[i] << " " << endl;
}
//归并排序
int arr4[] = {57, 68, 59, 52, 72, 28, 96, 33, 24};
sortObj->MergeSort(arr4, sizeof(arr4) / sizeof(arr4[0]));
cout << "MergeSort:"<< endl;
for(int i = 0; i < sizeof(arr4) / sizeof(arr4[0]); i++)
{
cout << arr4[i] << " " << endl;
}
//快速排序
int arr5[] = {57, 68, 59, 52, 72, 28, 96, 33, 24};
sortObj->QuickSort(arr5, 0, sizeof(arr5) / sizeof(arr5[0]-1));
cout << "MergeSort:"<< endl;
for(int i = 0; i < sizeof(arr5) / sizeof(arr5[0]); i++)
{
cout << arr5[i] << " " << endl;
}
//堆排序
int arr6[] = {57, 68, 59, 52, 72, 28, 96, 33, 24};
sortObj->HeapSort(arr6, sizeof(arr6) / sizeof(arr6[0]));
cout << "HeapSort:"<< endl;
for(int i = 0; i < sizeof(arr6) / sizeof(arr6[0]); i++)
{
cout << arr6[i] << " " << endl;
}
}
