排序算法合集

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>

#include<assert.h>

#include<cstdlib>

using namespace std;

//直接插入排序

//思路：保留第一個，取第二個和第一個進行比較，如果第二個大于第一個直接插入數組第二個位置，否則

//將第一個向后移動一位，將第二個數據插入第一個位置，再取第三個數據與第二個進行比較以此類推……

void Insertsort(int *a, size_t size)

{

assert(a);

for (size_t i = 1; i < size; i++)

{

int index = i;

int temp = a[index];

int end = index - 1;

while (end >= 0 && temp<a[end])

{

a[end+1] = a[end];//向后移動；

end--;//調試一下你就知道怎么回事

}

a[end+1] = temp;//插入

}

}

//希爾排序

void ShellSort(int *a, size_t size)

{

assert(a);

int gap = (size / 3) + 1;

while (gap >0)

{

for (int i = gap; i < size; i++)

{

int index = i;

int tmp = a[index];

int end = index - gap;

while (end >= 0 && tmp < a[end])

{

a[end + gap] = a[end];

end -= gap;

}

a[end + gap] = tmp;

}

           gap /=3;

}

}

//void ShellSort(int a[], int n)  

//{

// int j, gap;

// gap = n/2;

// while (gap > 0)

// {

// //for (gap = n / 2; gap > 0; gap /= 2)

// for (j = gap; j < n; j++)//從數組第gap個元素開始  

// if (a[j] < a[j - gap])//每個元素與自己組內的數據進行直接插入排序  

// {

// int temp = a[j];

// int k = j - gap;

// while (k >= 0 && a[k] > temp)

// {

// a[k + gap] = a[k];

// k -= gap;

// }

// a[k + gap] = temp;

// }

// gap /= 2;

// }

//

//}

//堆排

//向下調整

void AdjustDown(int *a, size_t size, int root)

{

int child = 2 * root + 1;

while (child < size)

{

if (child + 1 < size&&a[child + 1] > a[child])

{

++child;

}

if (a[child] > a[root])

{

swap(a[child], a[root]);

root = child;

child = 2 * root + 1;

}

else

{

break;

}

}

}

void HeapSort(int *a, size_t size)

{

assert(a);

for (int i = (size - 2) / 2; i >= 0; i--)

{

AdjustDown(a, size, i);

}

for (size_t i = 0; i < size; ++i)

{

swap(a[0], a[size -1- i]);

AdjustDown(a, size -1- i, 0);

}

}

//選擇排序

void SelectionSort(int*a, size_t size)

{

for (int i = 0; i < size; i++)

{

int index=i;//保存最小的數

for (int j = i+1; j < size; j++)//j=i+1 ？因為前面已經有序，所以不用送1開始而是從1+i開始的；

{

if (a[j] < a[index])

{

index = j;//保存下最小的數的下標

}

}

if (index != i)//排之前已經是一個序列，所以需要進行交換。

{

int tmp = a[index];

a[index] = a[i];

a[i] = tmp;

}

}

}

//選擇排序的優化

void SelectSort(int *a, size_t size)

{

int left = 0;

int right = size - 1;

for (; left < right; left++, right--)

{

int max = left;

int min = right;

for (int i = left; i<=right;i++)//一次循環找出其中的最大值和最小值,

{

if (a[min]>a[i])

{

min = i;

}

else if (a[max] < a[i])

{

max = i;

}

   }

if (left != min)

{

int temp = a[min];

a[min] = a[left];

a[left] = temp;

if (max == left)

{

max = min;

}

}

if (right != max)

{

int tmp = a[max];

a[max] = a[right];

a[right] = tmp;

if (min == right)

{

min = max;

}

}

}

}

//冒泡排序

void BubbleSort(int *a, size_t size)

{

for (int i = 1; i < size; i++)

{

for (int j = 0; j < size-i; j++)

{

if (a[j]>a[j + 1])

{

int tmp = a[j];

a[j] = a[j + 1];

a[j + 1] = tmp;

}

}

}

}

//快速排序

int PartSort(int *a, int left,int right)

{

int MidOfThree(int *a, int left, int right);

int begin = left;

int end = right-1;

int key = MidOfThree(a,left,right);

while (begin < end)

{

while (begin < end && a[begin] <= key)

{

++begin;

}

while (end > begin && a[end] >= key)

{

--end;

}

swap(a[begin], a[end]);

}

if (a[begin]>a[right])

{

swap(a[begin], a[right]);

return begin;

}

else

{

return right;

}

}

void QuickSort(int*a,int left,int right)

{

assert(a);

if (left < right)

{

int boundary = PartSort(a, left, right);

QuickSort(a, left, boundary - 1);

QuickSort(a, boundary + 1, right);

}

}

//快速排序之挖坑填數

void QuickSort1(int*a, int left, int right)

{

assert(a);

if (left < right)

{

int begin = left;

int end = right;

int key = a[left];

while (begin < end)

{

while (begin < end&&a[end] >= key)

{

--end;

}

a[begin] = a[end];

while (begin < end&&a[begin] <= key)

{

++begin;

}

a[end] = a[begin];

}

a[begin] = key;

QuickSort1(a, left, begin - 1);

QuickSort1(a, begin + 1, right);

}

}

//優化快速排序

//快速排序的優化-三數取中法

int MidOfThree(int *a, int left, int right)

{

int mid = left + (right - left) / 2;

if (a[mid] < a[left])

{

swap(a[mid], a[left]);

}

if (a[left]>a[right])

{

swap(a[left], a[right]);

}

if (a[mid] > a[right])

{

swap(a[mid], a[right]);

}

return a[mid];

//a[left]<a[mid]<a[right]

}

//歸并排序法

//{begin.....mid,mid+1.....end}

void MergeArray(int *a, int begin, int mid, int end, int*tmp)//使兩個數組有序然后合并

{

int i = begin;

int m = mid;

int j = mid + 1;

int k = end;

int n = 0;

while (i <= m && k >= j)

{

if (a[i] <= a[j])

{

tmp[n++] = a[i++];

}

else

{

tmp[n++] = a[j++];

}

}

while (i <= m)

{

tmp[n++] = a[i++];

}

while (j <= k)

{

tmp[n++] = a[j++];

}

for (int i = 0; i < n; i++)

{

a[begin+i] = tmp[i];

}

} 

void _MergeSort(int *a, int left, int right,int *tmp)

{

if (left < right)

{

int mid = left + (right - left) / 2;//將數列分成兩半，再將每一半排序

_MergeSort(a, left, mid, tmp);       //有點像將兩個有序的單鏈表合并后依然有序

_MergeSort(a, mid + 1, right, tmp);

MergeArray(a, left, mid, right, tmp);

}

}

void MergeSort(int *a, size_t size)

{

int *tmp = new int[size];

if (tmp != NULL) 

{

_MergeSort(a, 0, size - 1, tmp);

}

delete[]tmp;

}

//計數排序

//int a[10] = { 2, 0, 4, 9, 3, 6, 8, 7, 1, 5 };

void CountSort(int *a, size_t size)

{

assert(a);

int max = a[0];

int min = a[0];

for (size_t i = 0; i < size; i++)

{

if (a[i]>max)

{

max = a[i];

}

if (a[i] < min)

{

min = a[i];

}

}

int range = max - min + 1;

int *countarray = new int[range];

memset(countarray, 0, sizeof(int)*range);

for (size_t i = 0; i < size; i++)

{

countarray[a[i] - min]++;

}

size_t index = 0;

for (int i = 0; i <= range; i++)

{

while (countarray[i]-->0)

{

a[index++] = min + i;

}

}

//delete[] countarray;

//countarray = NULL;

}

//基數排序

int GetMaxDigit(int *a, size_t size)

{

int digit = 1;

int max = 10;

for (size_t i = 0; i < size; i++)

{

while (a[i]>=max)

{

++digit;

max *= 10;

}

}

return digit;

}

void DigitSortLSD(int* a, size_t size)

{

assert(a);

int MaxBit = GetMaxDigit(a, size);   //獲取最大位數

int* bucket = new int[size];     //為bucket開辟空間

int count[10];

int start[10];

int bit = 1;

int digit = 1;

while (bit <= MaxBit)

{

memset(count, 0, sizeof(int)* 10);

memset(start, 0, sizeof(int)* 10);

//統計0-9號桶中共有多少個數據

for (size_t i = 0; i < size; ++i)

{

int num = (a[i] / digit) % 10;  //每個數字模10，取余數，即為個位數字的值，存入相應的位置，個數加1

count[num]++;

}

//計算個數為0-9  的在桶里的起始位置

start[0] = 0;

for (size_t i = 1; i < size; ++i)

{

start[i] = start[i - 1] + count[i - 1];

}

for (size_t i = 0; i < size; ++i)

{

int num = a[i] % 10;

bucket[start[num]++] = a[i];

}

//將桶中的數據拷貝回去

memcpy(a, bucket, sizeof(int)* 10);

digit *= 10;

++bit;

}

}

void Test()

{

int a[10] = { 2, 3, 1, 4, 5, 6, 9, 7, 8, 0 };

Insertsort(a, 10);

for (int i = 0; i < 10; i++)

{

cout << a[i] << " ";

}

cout << endl;

}

void Test1()

{

int a[10] = { 2, 5, 4, 9, 3, 6, 8, 7, 1, 0 };

ShellSort(a, 10);

for (int i = 0; i < 10; i++)

{

cout << a[i] << " ";

}

cout << endl;

}

void Test2()

{

int a[10] = { 4, 5, 1, 2, 3, 6, 9, 0, 8, 7 };

HeapSort(a, 10);

for (int i = 0; i < 10; i++)

{

cout << a[i] << " ";

}

cout << endl;

}

void Test3()

{

int a[10] = { 2, 5, 4, 9, 3, 6, 8, 7, 1, 0 };

SelectSort(a, 10);

for (int i = 0; i < 10; i++)

{

cout << a[i] << " ";

}

cout << endl;

}

void Test4()

{

int a[10] = { 2, 5, 4, 9, 3, 6, 8, 7, 1, 0 };

SelectionSort(a, 10);

for (int i = 0; i < 10; i++)

{

cout << a[i] << " ";

}

cout << endl;

}

void Test5()

{

int a[10] = { 2, 5, 4, 9, 3, 6, 8, 7, 1, 0 };

    BubbleSort(a,10);

for (int i = 0; i < 10; i++)

{

cout << a[i] << " ";

}

cout << endl;

}

void Test6()

{

int a[10] = { 2, 0, 4, 9, 3, 6, 8, 7, 1, 5 };

QuickSort(a, 0, 9);

for (int i = 0; i < 10; i++)

{

cout << a[i] << " ";

}

cout << endl;

}

void Test7()

{

int a[10] = { 2, 0, 4, 9, 3, 6, 8, 7, 1, 5 };

MergeSort(a,10);

for (int i = 0; i < 10; i++)

{

cout << a[i] << " ";

}

cout << endl;

}

void Test8()

{

int a[10] = { 2, 0, 4, 9, 3, 6, 3, 3, 1, 5 };

CountSort(a, 10);

for (int i = 0; i < 10; i++)

{

cout << a[i] << " ";

}

cout << endl;

}

void Test9()

{

int a[10] = { 2, 0, 4, 9, 3, 6, 8, 7, 1, 5 };

DigitSortLSD(a, 10);

for (int i = 0; i < 10; i++)

{

cout << a[i] << " ";

}

cout << endl;

}

int main()

{

Test();

Test1();

Test2();

Test4();

Test5();

Test6();

Test7();

Test8();

Test9();

system("pause");

return 0;

}