各类排序代码归纳（经过测试的）
以下各种排序算法是我自己跟着算法描述写的（有参考其他人的），直接贴到VS里就能用，如果要看懂的话还是需要了解一下各种排序算法的实现原理
#include <iostream>
#include <algorithm>
using namespace std;
int a[10] = { 0 };
void show_Result(int *c)
{
for (int i = 0; i < 10; ++i)
{
cout <<c[i] << " ";
}
cout << endl;
}
void show_Result2(int *c)
{
for (int i = 1; i < 11; ++i)
{
cout << c[i] << " ";
}
cout << endl;
}
/*冒泡排序*/
void maopao(int *a)
{
int temp = 0;
for (int i = 0; i < 10; i++)
{
for (int j = 0; j < 10-1-i; j++)
{
if (a[j]>a[j+1])
{
temp = a[j + 1];
a[j + 1] = a[j];
a[j] = temp;
}
}
}
}
/*/快速排序*/
void Quick_Sort(int first,int last)
{
int base = a[first];
int left = first;
int right = last;
int temp = 0;
if (left > right)
{
return;
}
while (left!=right)
{
while (left<right)
{
if (a[right]<base)
{
break;
}
--right;
}
while (left<right)
{
if (a[left] > base)
{
break;
}
++left;
}
if (left != right)
{
temp = a[left];
a[left] = a[right];
a[right] = temp;
}
}
if (left == right)
{
a[first] = a[left];
a[left] = base;
}
//show_Result(b);
//cout << endl;
Quick_Sort(first, left - 1);
Quick_Sort(left + 1, last);
}
/*/桶排序*/
void tong_Sort(int *a)
{
int b[10] = {0};
for (int i = 0; i < 10; i++)
{
b[a[i]]++;
}
for (int i = 0; i < 10; i++)
{
for (int j = b[i]; j > 0; j--)
{
cout << i << " ";
}
}
cout << endl;
}
/*/堆排序*/
#pragma region MyRegion
int n = 10;//元素个数
int b[11] = { 0 };
//数据下调
void Sift_Down(int i)
{
int temp = 0;//值交换时使用
int flag = 0;//结束下调
while (2 * i <= n &&flag == 0)
{
int last_sift = i;
if (b[i] > b[2 * i])//和左节点比较
{
last_sift = 2 * i;//记录较小值的节点
}
if (2 * i + 1 <= n&&b[last_sift] > b[2 * i + 1])//和右节点比较
{
last_sift = 2 * i + 1;//记录较小值的节点
}
if (last_sift != i)
{
temp = b[i];
b[i] = b[last_sift];
b[last_sift] = temp;
i = last_sift;//如果最小节点就是根节点那么结束数据下调
}
else
{
flag = 1;
}
}
}
//数据出堆，将最后一个结点的数据放在最上面
int deleteMax()
{
int temp = 0;
temp = b[1];
b[1] = b[n];
n--;
Sift_Down(1);
return temp;
}
void heap_Sort()
{
//建立最小堆
for (int i = n / 2; i > 0; --i)
{
Sift_Down(i);
}
int num = n;
//数据出堆
for (int i = 1; i <= num; i++)
{
cout << deleteMax() << " ";
}
}
#pragma endregion
/*归并排序*/
void guibingarry(int a[], int first, int mid,int last, int temp[])//将有序的两个序列按顺序合并
{
int i = first;
int j = mid + 1;
int n = mid;
int m = last;
int k = 0;
while (i <= n&&j <= m)
{
if (a[i] < a[j])
{
temp[k++] = a[i++];
}
else
{
temp[k++] = a[j++];
}
}
while (i <= n)
{
temp[k++] = a[i++];
}
while (j <= m)
{
temp[k++] = a[j++];
}
for (i = 0; i < k; i++)
{
a[first + i] = temp[i];
}
}
void guibingSort(int a[],int first,int last,int temp[] )//先将序列拆分
{
if (first < last)
{
int mid = (first+last)/2;
guibingSort(a,first,mid,temp);
guibingSort(a, mid + 1, last, temp);
guibingarry(a,first,mid,last,temp);
}
}
void Gui_bingSort(int a[],int n)
{
int *p = new int[n];
guibingSort(a,0,n-1,p);
delete [] p;
}
/*直接插入排序*/
void dir_insert_sort(int qa[],int number)
{
int i = 0;
int j = 0;
int min_set =0 ;
int temp =0;
for (i = 0; i < number; i++)
{
min_set = i;//如果扫描不出来则不换位置
for (j = 0; j < i; j++)//从头开始扫描，记录比较后的位置
{
if (qa[i] <= qa[j])
{
min_set = j;
temp = qa[i];
break;
}
}
for (j =i ; j > min_set; j--)
{
qa[j] = qa[j-1];
}
if(min_set!=i)
qa[min_set] = temp;
}
}
/*希尔排序*/
void shell_sort(int a[],int n)
{
int add = 5;//设置步长
int number = n /add;//每次能够进行排序的数目
while (add)
{
number = n / add;
for (int j = 0;j<add; j++)
{
int *p = new int[number];
//cout << number << endl;
for (int i = 0; i < number; i++)
{
p[i] = a[i*add + j];
}
dir_insert_sort(p, number);
for (int i = 0; i < number; i++)
{
a[i*add+j] = p[i];
}
delete[]p;
}
if (add == 1)
{
break;
}
add = add - 2;
if (add < 1)
{
add = 1;
}
}
}
int main()//需要排序的数据生成及输出显示
{
for (int i = 0; i < 10; ++i)
{
a[i] = i;
}
for (int i = 1; i < 11; ++i)
{
b[i] = i;
}
cout << "maopao:" << endl;//冒泡排序
random_shuffle(a,a+9);
show_Result(a);
maopao(a);
show_Result(a);
cout << "quick_sort:" << endl;//快速排序
random_shuffle(a, a + 9);
show_Result(a);
Quick_Sort(0, 9);
show_Result(a);
cout << "heap_sort:" << endl;//堆排序
random_shuffle(b+1, b + 10);
show_Result2(b);
heap_Sort();
cout << endl;
cout << "tong_Sort:" << endl;//桶排序
random_shuffle(a, a + 9);
show_Result(a);
tong_Sort(a);
//show_Result(a);
cout << "guibing_Sort:" << endl;//归并排序
random_shuffle(a, a + 9);
show_Result(a);
Gui_bingSort(a,10);
show_Result(a);
cout << "dir_insert_sort:" << endl;//直接插入排序
random_shuffle(a, a + 9);
show_Result(a);
dir_insert_sort(a,10);
show_Result(a);
cout << "shell_sort:" << endl;//希尔排序
random_shuffle(a, a + 9);
show_Result(a);
shell_sort(a,10);
show_Result(a);
system("pause");
return 0;
}
结果：
相关推荐
要知道时间复杂度只是描述一个增长趋势，复杂度为O的排序算法执行时间不一定比复杂度为O长，因为在计算O时省略了系数、常数、低阶。实际上，在对小规模数据进行排序时，n2的值实际比 knlogn+c还要小。