各种排序算法代码

各种排序算法代码

#include <iostream>
#include <ctime>
const int SIZE = 100;
const int MAX = 1000;
using namespace std;
void Swap(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
void BubbleSort(int *arr, int size)
{
int i, j;
for(i=0;i<size-1;i++)
for(j=size-1;j>i;j--)
if(arr[j] < arr[j-1])
Swap(arr[j], arr[j-1]);
}
void SelectionSort(int *arr, int size)
{
int i, j, min;
for(i=0;i<size-1;i++)
{
min = i;
for(j=i+1;j<size;j++)
if(arr[min] > arr[j])
min = j;
Swap(arr[i], arr[min]);
}
}
void InsertSort(int *arr, int size)
{
int fOut, loc, temp;
for(fOut=1;fOut<size;fOut++)
if(arr[fOut] < arr[fOut-1])
{
temp = arr[fOut];
loc = fOut;
do
{
arr[loc] = arr[loc-1];
loc--;
}while(loc>0 && arr[loc-1]>temp);
arr[loc] = temp;
}
}
int Partition(int *arr, int first, int last)
{
int i, small, x;
swap(arr[first], arr[ (first+last)/2 ]);
x = arr[first];
small = first;
for(i=first+1;i<=last;i++)
if(arr[i] < x)
{
small++;
swap(arr[small], arr[i]);
}
swap(arr[first], arr[small]);
return small;
}
void RecQuick(int *arr, int first, int last)
{
int pivotLoc;
if(first < last)
{
pivotLoc = Partition(arr, first, last);
RecQuick(arr, first, pivotLoc-1);
RecQuick(arr, pivotLoc+1, last);
}
}
void QuickSort(int *arr, int size)
{
RecQuick(arr, 0, size-1);
}

void Merge(int *arr, int start, int mid, int end)
{
int temp1[SIZE], temp2[SIZE];
int n1, n2;
int i, j, k;
n1 = mid - start + 1;
n2 = end - mid;
for(i=0;i<n1;i++)
temp1[i] = arr[start + i];
for(i=0;i<n2;i++)
temp2[i] = arr[mid + i + 1];
temp1[n1] = temp2[n2] = INT_MAX;
i = j = 0;
for(k=start;k<=end;k++)
{
if(temp1[i] <= temp2[j])
{
arr[k] = temp1[i];
i++;
}
else
{
arr[k] = temp2[j];
j++;
}
}
}
void RecMerge(int *arr, int start, int end)
{
int i;
if(start < end)
{
i = (start + end) / 2;
RecMerge(arr, start, i);
RecMerge(arr, i+1, end);
Merge(arr, start, i, end);
}
}
void MergeSort(int *arr, int size)
{
RecMerge(arr, 0, size-1);
}
void Heapify(int *arr, int low, int high)
{
int large;
int temp = arr[low];
large = 2 * low + 1;
while(large <= high)
{
if(large<high && arr[large]
<arr[large+1])
large = large + 1;
if(temp > arr[large])
break;
else
{
arr[low] = arr[large];
low = large;
large = 2 * low + 1;
}

各种排序算法代码

}
arr[low] = temp;
}
void BuildHeap(int *arr, int size)
{
int i;
for(i=size/2-1;i>=0;i--)
Heapify(arr, i, size-1);
}
void HeapSort(int *arr, int size)
{
int i;
BuildHeap(arr, size);
for(i=size-1;i>=0;i--)
{
swap(arr[0], arr[i]);
Heapify(arr, 0, i-1);
}
}
void ShellSort(int *arr, int size)
{
int i, j, k, temp;
for(i=size/2;i>0;i/=2)
{
for(j=i;j<size;j+=i)
{
temp = arr[j];
k = j;
while(k-i>=0 && temp<arr[k-i])
{
arr[k] = arr[k-i];
k -= i;
}
arr[k] = temp;
}
}
}
void Print(int *arr, int size)
{
int i;
for(i=0;i<size;i++)
{
printf("%6d ", arr[i]);
if(0 == (i+1) % 10)
cout << endl;
}
cout << endl;
}
int xuanze()
{ int a;
cout<<"是否返回继续操作？是<1>，否<0>。"<<endl;
cin>>a;
return a;
}
int main()
{
int arr[SIZE], y,i,sel;
cout << "The array is: " << endl;
srand((unsigned)time(0));
for(i=0;i<SIZE;i++)
arr[i] = rand() % MAX;
while (1)
{
system("cls");
cout<<"在1000以内随机产生100个数为："<<endl;
Print(arr, SIZE);
cout<<"==========================排序选择的基本操作菜单========================"<<endl;
cout<<"\t1、冒泡排序。"<<endl;
cout<<"\t2、直接插入排序。"<<endl;
cout<<"\t3、简单选择排序"<<endl;
cout<<"\t4、快速排序。"<<endl;
cout<<"\t5、希尔排序。"<<endl;
cout<<"\t6、堆排序。"<<endl;
cout<<"\t7、退出操作。"<<endl;
cout<<"-----------------------------------------------------------------------"<<endl;
cout<<"请输入选择要执行的编号(1-7)：";
cin>>sel;
cout<<"-----------------------------------------------------------------------"<<endl;
switch (sel)
{case 1:BubbleSort(arr, SIZE);
cout<<"经过排序后的结果是："<<endl;
Print(arr, SIZE);
break;
case 2:InsertSort(arr, SIZE);
cout<<"经过排序后的结果是："<<endl;
Print(arr, SIZE);
break;
case 3:SelectionSort(arr, SIZE);
cout<<"经过排序后的结果是："<<endl;
Print(arr, SIZE);
break;
case 4:QuickSort(arr, SIZE);
cout<<"经过排序后的结果是："<<endl;
Print(arr, SIZE);
break;
case 5:ShellSort(arr, SIZE);
cout<<"经过排序后的结果是："<<endl;
Print(arr, SIZE);
break;
case 6:MergeSort(arr, SIZE);
cout<<"经过排序后的结果是："<<endl
;
Print(arr, SIZE);
break;
case 7:return 0;
cout<<endl;
};
y=xuanze();
if(y==0)
exit(0);
else
fflush(stdin);
}
return 0;
}