#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;
}
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
