using System;
using System.Collections;
using System.Collections.Concurrent;
using System.Runtime.CompilerServices;
namespace DemoApplication
{
struct KeyType
{
public int key;
};
struct SqList
{
public KeyType[] r;
public int length;
};
class Demo
{
static int maxSize = 100;
private static void BInsertSort(SqList l)
{
KeyType temp;
Console.WriteLine("排序前:l.key:{0}, l.length:{1}", StrSqList(l), l.length);
for (int i = 1; i < l.length; i++)
{
temp = l.r[i];
int low = 0;
int high = i - 1;
while (low <= high)
{
int m = (low + high) / 2;
if (temp.key < l.r[m].key)
{
high--;
} else
{
low++;
}
}
for (int j = i - 1; j >= high + 1; j--)
{
l.r[j + 1].key = l.r[j].key;
}
l.r[high + 1].key = temp.key;
// Console.WriteLine("排序中:l.key:{0}, l.length:{1}", StrSqList(l), l.length);
}
Console.WriteLine("排序后:l.key:{0}, l.length:{1}", StrSqList(l), l.length);
}
private static void ShellInsert(SqList l, int dk)
{
// l 按照增量dk 插入排序
// 希尔插入排序算法
KeyType temp;
for(int i = dk; i < l.length; i++)
{
if (l.r[i].key < l.r[i-dk].key)
{
temp = l.r[i];
l.r[i].key = l.r[i - dk].key;
int j = i - 2 * dk;
for (; j >= 0; j-=dk)
{
if (temp.key < l.r[j].key) {
l.r[j + 1].key = l.r[j].key;
}
else
{
break;
}
}
l.r[j+dk].key = temp.key;
}
}
}
private static void ShellSort(SqList l)
{
Console.WriteLine("排序前:l.key:{0}, l.length:{1}", StrSqList(l), l.length);
ShellInsert(l, 5);
Console.WriteLine("第一趟排序后:l.key:{0}, l.length:{1}", StrSqList(l), l.length);
ShellInsert(l, 3);
Console.WriteLine("第二趟排序后:l.key:{0}, l.length:{1}", StrSqList(l), l.length);
ShellInsert(l, 1);
Console.WriteLine("排序后:l.key:{0}, l.length:{1}", StrSqList(l), l.length);
}
private static string StrSqList(SqList l)
{
int []a = new int[l.length];
for(int i=0; i < l.length; i++)
{
a[i] = l.r[i].key;
}
return string.Join(",", a);
}
private static int Partition(SqList l, int low, int high)
{
// 快速排序分割
int pivotkey = l.r[low].key;
while (low < high)
{
while (low < high && l.r[high].key >= pivotkey) high--;
l.r[low].key = l.r[high].key;
while (low < high && l.r[low].key <= pivotkey) low++;
l.r[high].key = l.r[low].key;
}
l.r[low].key = pivotkey;
return low;
}
private static void QSort(SqList l, int low, int high)
{
// 递归调用
if (low < high)
{
int m = Partition(l, low, high);
QSort(l, low, m - 1);
QSort(l, m + 1, high);
}
}
private static void QuickSort(SqList l)
{
Console.WriteLine("排序前:l.key:{0}, l.length:{1}", StrSqList(l), l.length);
QSort(l, 0, l.length - 1);
Console.WriteLine("排序后:l.key:{0}, l.length:{1}", StrSqList(l), l.length);
}
static void Main(string[] args)
{
/* 我的第一个 C# 程序*/
// 初始化线性表
SqList l;
l.r = new KeyType[maxSize];
int []r = new int[]{49,38,65,97,76,13,27,49,55,4 };
KeyType key;
for(int i = 0; i < r.Length; i++)
{
key.key = r[i];
l.r[i] = key;
}
l.length = r.Length;
// 调用排序算法
QuickSort(l);
Console.ReadKey();
}
}
}