Zi 字媒體
2017-07-25T20:27:27+00:00
C++經典的7種排序演算法
剛才在網路上閒晃，發現C++經典的7種排序演算法的程式碼，馬上實測驗證，確定可用，趕緊PO出來和大家分享，有興趣的同好歡迎來(C/P)一下。
#include
#include
using namespace std;
//C++經典的7種排序演算法
/*
參考網頁:: http://www.caogenit.com/caogenxueyuan/yingyongfangxiang/rengongzhineng/1724.html
*/
//////////////////////////////////////
void SelectSort(int* array, int size);
void InsertSort(int* array, int size);
void BubbleSort(int* array, int size);
void MergeSort(int* array, int left, int right);
void Merge(int* array, int left, int mid, int right);
void HeapSort(int *array, int size);
void HeapAjust(int *array, int toAjust, int size);
void QuickSort(int *array, int left, int right);
void TreeSort(int *array, int size);
void TreeMidRetrival(int* array, int* temp, int pos, int* lChild, int* rChild);
void Swap(int* array, int x, int y);
/////////////////////////////////////////
void Swap(int* array, int x, int y)
{
int temp = array[x];
array[x] = array[y];
array[y] = temp;
}
//選擇排序
void SelectSort(int* array, int size)
{
int minIndex;
for(int i = 0; i < size; i++)
{
minIndex = i;
for(int j = i + 1; j < size; j++)
{
if(array[minIndex] > array[j])
{
minIndex = j;
}
}
if(minIndex != i)
{
Swap(array, i, minIndex);
}
}
}
//氣泡排序
void BubbleSort(int* array, int size)
{
for(int i = 0; i < size; i++)
{
for(int j = 1; j < size – i; j++)
{
if(array[j] < array[j – 1])
{
Swap(array, j, j – 1);
}
}
}
}
//插入排序
void InsertSort(int* array, int size)
{
for(int i = 1; i < size; i++)
{
for(int j = i; j > 0; j–)
{
if(array[j] < array[j – 1])
{
Swap(array, j, j–1);
}
}
}
}
//快速排序
void QuickSort(int* array, int left, int right)
{
if(left < right)
{
int i = left –1, j = right + 1;
int mid = array[(left + right) / 2];
while(true)
{
while(array[++i] < mid);
while(array[–j] > mid);
if(i >= j)
{
break;
}
Swap(array, i, j);
}
QuickSort(array, left, i – 1);
QuickSort(array, j + 1, right);
}
}
void Merge(int* array, int left, int mid, int right)
{
int* temp = new int[right – left + 1];
int i = left, j = mid + 1, m = 0;
while(i <= mid && j <= right)
{
if(array[i] < array[j])
{
temp[m++] = array[i++];
}
else
{
temp[m++] = array[j++];
}
}
while(i <= mid)
{
temp[m++] = array[i++];
}
while(j <= right)
{
temp[m++] = array[j++];
}
for(int n = left, m = 0; n <= right; n++, m++)
{
array[n] = temp[m];
}
delete temp;
}
//歸併排序
void MergeSort(int* array, int left, int right)
{
if(left < right)
{
int mid = (left + right) / 2;
MergeSort(array, left, mid);
MergeSort(array, mid + 1, right);
Merge(array, left, mid, right);
}
}
//調整堆
void HeapAjust(int *array, int toAjust, int size)
{
int pos = toAjust;
while((pos * 2 + 1) < size)
{
int lChild = pos * 2 + 1;
if(array[lChild] > array[pos])
{
pos = lChild;//左孩子大
}
int rChild = lChild + 1;
if(rChild < size && array[rChild] > array[pos])
{
pos = rChild;//右孩子更大
}
if(pos != toAjust) //父結點比其中一個孩子小
{
Swap(array, toAjust, pos);
toAjust = pos;
}
else
{
break;
}
}
}
//堆排序
void HeapSort(int* array, int size)
{
int lastP = size / 2;
//從最後一個有孩子的結點開始建初始堆
for(int i = lastP – 1; i >= 0; i–)
{
HeapAjust(array, i, size);
}
int j = size;
//將堆頂元素和無序區間的最後一個元素交換，再調整堆
while(j > 0)
{
Swap(array, 0, j – 1);
j–;
HeapAjust(array, 0, j);
}
}
//樹排序
void TreeSort(int* array, int size)
{
int *parent = new int[size];//父結點子針
int *lChild = new int[size];//左孩子子針
int *rChild = new int[size];//右孩子子針
//將各結點左右子結點指標均置為-1，表示沒有左右子結點
for(int i = 0; i < size; i++)
{
lChild[i] = –1;
rChild[i] = –1;
}
parent[0] = –1; //將第一個元素作為根結點，其父結點置為-1
//從第2個數開始構造樹
for(int i = 1; i < size; i++)
{
int last = 0;
while(true)
{
int compare = array[i] – array[last];
if(compare > 0) //比當前值大，進入右子樹
{
if(rChild[last] == –1)
{
rChild[last] = i;
parent[i] = last;
break;
}
else
{
last = rChild[last];
}
}
else //比當前值小，進入左子樹
{
if(lChild[last] == –1)
{
lChild[last] = i;
parent[i] = last;
break;
}
else
{
last = lChild[last];
}
}
}
}
//保存排序樹的中序遍歷結果
int* midRetrival = new int[size];
TreeMidRetrival(array, midRetrival, 0, lChild, rChild);
//將排好序的中序數組複製到原陣列
for(int i = 0; i < size; i++)
{
array[i] = midRetrival[i];
}
}
//中序遍歷
void TreeMidRetrival(int *array, int* temp, int pos, int* lChild, int* rChild)
{
static int i = 0;
if(pos != –1)
{
TreeMidRetrival(array, temp, lChild[pos], lChild, rChild);//遍歷左子樹
temp[i++] = array[pos];//保存當前值
TreeMidRetrival(array, temp, rChild[pos], lChild, rChild);//遍歷右子樹
}
else
{
return;
}
}
int main()
{
int i;
int intdata[5]={5,3,1,2,4};
printf(“before: “);
for(i=0;i<5;i++)
{
printf(“%d\t”,intdata[i]);
}
printf(“\n”);
//SelectSort(intdata, 5);
//InsertSort(intdata, 5);
BubbleSort(intdata, 5);
//MergeSort(intdata, 0, 4);
//HeapSort(intdata, 5);
//QuickSort(intdata, 0, 4);
//TreeSort(intdata, 5);
printf(“after: “);
for(i=0;i<5;i++)
{
printf(“%d\t”,intdata[i]);
}
printf(“\n”);
cout << “Hello world!” << endl;
return 0;
}
寫了
5860316篇文章，獲得
23313次喜歡