希爾排序晶疼,快速排序,堆排序锭吨,2路歸并算法的c++簡單實現(xiàn)
#include <iostream>
#include <ctime>
#include <cmath>
using namespace std;
//對數(shù)列做一趟增量為d的希爾插入排序
void shellInsert(int *list, int length, int d)
{
for (int i = d; i < length; i++)
{
//間隔為d的插入排序
if (list[i] < list[i - d])
{
int temp = list[i];
int j;
//向左查找最終插入位置寒匙,查找的同時順便右搬數(shù)據(jù)
for (j = i - d; j >= 0 && temp < list[j]; j -= d)
list[j + d] = list[j];
list[j + d] = temp;
}
}
}
//希爾排序(升序)
void shellSort(int *list, int length)
{
//以{2^n-1}為增量序列
for (int d = 1 << (int)log2(length); d >= 2; d >>= 1)
shellInsert(list, length, d - 1);
}
//快速排序(升序)
void quickSort(int *list, int length)
{
if (length <= 1) return;
//隨機選取信標
int pivot = list[rand() % length];
int i = 0, j = length - 1;
while (i != j)
{
while (i != j && list[i] < pivot)
i++;
while (i != j && list[j] >= pivot)
j--;
swap(list[i], list[j]);
}
quickSort(list, i);
quickSort(list + i, length - i);
}
//堆排序(升序)
void heapSort(int *list, int length)
{
int heap[length + 1] = {0};
//建堆
for (int i = 1; i <= length; i++)
{
heap[i] = list[i - 1];
for (int j = i; j > 1 && heap[j] < heap[j / 2]; j /= 2)
swap(heap[j], heap[j / 2]);
}
//彈出锄弱,重調(diào)整
for (int i = 0, j = length; i < length; i++, j--)
{
list[i] = heap[1];
swap(heap[1], heap[j]);
for (int k = 2; k < j; k *= 2)
{
//從2個孩子(或只有1個孩子)中選取最小的那個去比較
if (k + 1 < j && heap[k + 1] < heap[k])
k = k + 1;
if (heap[k] < heap[k / 2])
swap(heap[k], heap[k / 2]);
else
break;
}
}
}
//2路歸并排序(升序)
void mergeSort(int *list, int length)
{
if (length <= 1)
return;
int mid = length / 2;
mergeSort(list, mid);
mergeSort(list + mid, length - mid);
//2路歸并
int tempList[length];
int i = 0, j = mid, k = 0;
while (k < length)
{
if (j >= length || (i < mid && list[i] < list[j]))
tempList[k++] = list[i++];
if (i >= mid || (j < length && list[j] < list[i]))
tempList[k++] = list[j++];
}
for (k = 0; k < length; k++)
list[k] = tempList[k];
}
int main()
{
//初始化數(shù)列
int length;
cin >> length;
int *list = new int[length];
for (int i = 0; i < length; i++)
list[i] = i;
//隨機洗切數(shù)列
srand(time(0));
for (int i = length - 1; i > 0; i--)
swap(list[i], list[rand() % i]);
//打印排序前數(shù)列
for (int i = 0; i < length; i++)
cout << list[i] << " ";
cout << endl;
//shellSort(list, length);
//quickSort(list, length);
//heapSort(list, length);
mergeSort(list, length);
//打印排序后數(shù)列
for (int i = 0; i < length; i++)
cout << list[i] << " ";
cout << endl;
}
運行結果
在
int main()
里面寫了一個隨機數(shù)列生成肖卧,可以快速驗證算法的正確性
歡迎友好交流