using System;
using System.Collections.Generic;
using System.Text;
namespace 排序汇总
{
class Program
{
//********************主函数*****************
static void Main(string[] args)
{
Console.WriteLine("请输入待排序列个数n");
int n = int.Parse(Console.ReadLine());
Console.WriteLine("请分别输入待排序元素");
int[] Sqlist = new int[n + 1];
for (int i = 1; i < Sqlist.Length; i++) //原排列存储在一维数组里，每种算法中下标均从1开始
{
Sqlist[i] = int.Parse(Console.ReadLine());
}
Console.WriteLine("请选择排序方法：");
Console.WriteLine("1、直接插入排序 2、折半插入排序 3、二路插入排序 4、希尔排序 5、快速插入排序");
Console.WriteLine("6、冒泡排序 7、选择排序 8、堆排序 9、归并排序 10、基数排序算法");
while (true)
{
Console.WriteLine();
int number = int.Parse(Console.ReadLine());
Console.WriteLine();
if (number == 1) zhijiecharupaixu(Sqlist);
if (number == 2) zhebancharu(Sqlist);
if (number == 3) erlucharusuanfa(Sqlist);
if (number == 4) xierpaixu(Sqlist);
if (number == 5) kuaisucharu(Sqlist, n);
if (number == 6) maopaopaixu(Sqlist);
if (number == 7) xuanzepaixu(Sqlist);
if (number == 8) duipaixu(Sqlist);
if (number == 9) guibingpaixu(Sqlist);
if (number == 10) jishupaixu(Sqlist);
Console.WriteLine("该序列从小到大为：");
for (int i = 1; i < Sqlist.Length; i++)
{
Console.WriteLine(Sqlist[i]);
}
} //可循环选择输入
}
//***********直接插入算法************
static void zhijiecharupaixu(int[] Sqlist)
{
Console.WriteLine("***********直接插入算法************");
for (int i = 2; i < Sqlist.Length; i++)
{
if (Sqlist[i] < Sqlist[i - 1])
{
Sqlist[0] = Sqlist[i];
Sqlist[i] = Sqlist[i - 1];
int j;
for (j = i - 2; Sqlist[0] < Sqlist[j]; --j)
{
Sqlist[j + 1] = Sqlist[j];
}
Sqlist[j + 1] = Sqlist[0];
}
}
}
//***********折半插入算法************
static void zhebancharu(int[] Sqlist)
{
Console.WriteLine("***********折半插入算法************");
for (int i = 2; i < Sqlist.Length; i++)
{
Sqlist[0] = Sqlist[i];
int low = 1;
int high = i - 1;
int m;
while (low <= high)
{
m = (low + high) / 2;
if (Sqlist[0] < Sqlist[m]) high = m - 1;
else low = m + 1;
}
int j;
for (j = i - 1; j >= high + 1; --j) Sqlist[j + 1] = Sqlist[j];
Sqlist[j + 1] = Sqlist[0];
}
}
//***********二路插入算法************
static void erlucharusuanfa(int[] Sqlist)
{
Console.WriteLine("***********二路插入算法************");
int[] Sl = new int[Sqlist.Length];
bidir_insert(Sqlist, Sl, Sqlist.Length);
}
static void bidir_insert(int[] source, int[] dest, int len)
{
int first, last;
first = last = 1;
dest[1] = source[1];
for (int i = 2; i < len; i++)
{
if (dest[last] <= source[i])
{
dest[++last] = source[i];
}
else if (dest[first] >= source[i])
{
first = (first - 1 + len) % len;
dest[first] = source[i];
}
else
{
for (int index = (last - 1 + len) % len; ; index = (index - 1 + len) % len)
{
if (dest[index] <= source[i])
{
int mid = last++;
while (mid != index)
{
dest[(mid + 1) % len] = dest[mid];
mid = (mid - 1 + len) % len;
}
dest[(index + 1) % len] = source[i];
break;
}
}
}
}
for (int i = 1; i < len; ++i)
{
source[i] = dest[first];
first = (first + 1) % len;
}
}
//***********希尔排序算法************
static void xierpaixu(int[] Sqlist)
{
Console.WriteLine("***********希尔排序算法************");
int[] dlta = new int[5];
dlta[0] = 9;
for (int j = 1; j < 5; j++)
{
dlta[j] = dlta[j - 1] - 2;
}
for (int i = 0; i < 5; i++)
Shellinsert(Sqlist, dlta[i]);
}
static void Shellinsert(int[] sqlist, int dk)
{
for (int i = dk + 1; i < sqlist.Length; ++i)
{
if (sqlist[i] < sqlist[i - dk])
{
sqlist[0] = sqlist[i];
int j;
for (j = i - dk; j > 0 && sqlist[0] < sqlist[j]; j -= dk)
{
sqlist[j + dk] = sqlist[j];
}
sqlist[j + dk] = sqlist[0];
}
}
}
//***********快速排序算法************
static void kuaisucharu(int[] Sqlist, int n)
{
Console.WriteLine("***********快速排序算法************");
Qsort(Sqlist, 1, n);
}
static int Partition(int[] sqlist, int low, int high)
{
sqlist[0] = sqlist[low];
int pivotkey = sqlist[low];
while (low < high)
{
while (low < high && sqlist[high] >= pivotkey) --high;
sqlist[low] = sqlist[high];
while (low < high && sqlist[low] <= pivotkey) ++low;
sqlist[high] = sqlist[low];
}
sqlist[low] = sqlist[0];
return low;
}
static void Qsort(int[] sqlist, int low, int high)
{
int pivotkey;
if (low < high)
{
pivotkey = Partition(sqlist, low, high);
Qsort(sqlist, low, pivotkey - 1);
Qsort(sqlist, pivotkey + 1, high);
}
}
//***********冒泡排序算法************
static void maopaopaixu(int[] Sqlist)
{
Console.WriteLine("***********冒泡排序算法************");
for (int i = 1; i < Sqlist.Length - 1; i++)
{
int m;
for (int j = 1; j < Sqlist.Length - i; j++)
{
if (Sqlist[j] > Sqlist[j + 1])
{
m = Sqlist[j + 1];
Sqlist[j + 1] = Sqlist[j];
Sqlist[j] = m;
}
}
}
}
//***********选择排序算法************
static void xuanzepaixu(int[] Sqlist)
{
Console.WriteLine("***********选择排序算法************");
for (int i = 1; i < Sqlist.Length - 1; i++)
{
int min = i;
int h;
for (int j = i + 1; j < Sqlist.Length; j++)
{
if (Sqlist[j] < Sqlist[min])
{
min = j;
}
}
h = Sqlist[i];
Sqlist[i] = Sqlist[min];
Sqlist[min] = h;
}
}
//***********堆排序算法************
static void duipaixu(int[] Sqlist)
{
Console.WriteLine("***********堆排序算法************");
Heapsort(Sqlist);
}
static void HeapAdjust(int[] sqlist, int s, int m)
{
int rc = sqlist[s];
for (int j = 2 * s; j <= m; j *= 2)
{
if (j < m && sqlist[j] < sqlist[j + 1]) ++j;
if (rc >= sqlist[j]) break;
sqlist[s] = sqlist[j];
s = j;
}
sqlist[s] = rc;
}
static void Heapsort(int[] sqlist)
{
int m;
for (int i = (sqlist.Length - 1) / 2; i > 0; --i)
HeapAdjust(sqlist, i, sqlist.Length - 1);
for (int i = sqlist.Length - 1; i > 1; --i)
{
m = sqlist[1];
sqlist[1] = sqlist[i];
sqlist[i] = m;
HeapAdjust(sqlist, 1, i - 1);
}
}
//***********归并排序算法************
static void guibingpaixu(int[] Sqlist)
{
Console.WriteLine("***********归并排序算法************");
Msort(Sqlist, Sqlist, 1, Sqlist.Length - 1);
}
static void Merge(int[] SR, int[] TR, int i, int m, int n)
{
int j, k;
for (j = m + 1, k = i; i <= m && j <= n; ++k)
{
if (SR[i] <= SR[j]) TR[k] = SR[i++];
else TR[k] = SR[j++];
}
if (i <= m)
{
for (; i <= m; i++, k++)
TR[k] = SR[i];
}
if (j <= n)
{
for (; j <= n; j++, k++)
TR[k] = SR[j];
}
}
static void Msort(int[] SR, int[] TR1, int s, int t)
{
int[] TR2 = new int[TR1.Length];
int m;
if (s == t) TR1[s] = SR[s];
else
{
m = (s + t) / 2;
Msort(SR, TR2, s, m);
Msort(SR, TR2, m + 1, t);
Merge(TR2, TR1, s, m, t);
}
}
//***********基数排序算法************
static void jishupaixu(int[] Sqlist)
{
Console.WriteLine("***********基数排序算法************");
int[] res = RadixSort(Sqlist, 5);
}
public static int[] RadixSort(int[] Array, int digit)
{
for (int k = 1; k <= digit; k++)
{
int[] tmpArray = new int[Array.Length];
int[] tmpCount = new int[10] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
for (int i = 0; i < Array.Length; i++)
{
int tmpSp = Array[i] / (int)Math.Pow(10, k - 1) - (Array[i] / (int)Math.Pow(10, k)) * 10;
tmpCount[tmpSp] += 1;
}
for (int m = 1; m < 10; m++)
{
tmpCount[m] += tmpCount[m - 1];
}
for (int n = Array.Length - 1; n >= 0; n--)
{
int tmpSp = Array[n] / (int)Math.Pow(10, k - 1) - (Array[n] / (int)Math.Pow(10, k)) * 10;
tmpArray[tmpCount[tmpSp] - 1] = Array[n];
tmpCount[tmpSp] -= 1;
}
for (int p = 1; p < Array.Length; p++)
{
Array[p] = tmpArray[p];
}
}
return Array;
}
}
}
