工作之余，实现排序算法若干如下：
一，冒泡排序
/// <summary>
/// bubbleSort;
///
/// /*理解其实程序就是思路的复述而已*/
/// </summary>
/// <param name="desti">目标数组</param>
/// <param name="swapTimes">交换次数</param>
public static void BubleSort(ref int[] desti, ref int swapTimes)
{
int destiLen = desti.Length;
/******各重循环各行其是即可********/
//冒泡次数，因为最后一次已经是最小，所以destiLen - 1
for(int i = 0; i < destiLen - 1; i ++)
{
bool ins = true;
//各次冒泡；前面已冒泡元素的位置无需冒泡;
for(int j = 0; j < destiLen - i - 1; j ++)
{
if(desti[j] > desti[j + 1])
{
ins = false;
Swap.Swaper(ref desti[j], ref desti[j + 1]);
swapTimes ++;
}
}
if(ins)
break;
}
}
二，插入排序
/// <summary>
/// 原始插入排序
/// </summary>
/// <param name="dest">目标数组</param>
/// <param name="swapTimes">交换次数</param>
public static void InsertSort(ref int[] dest, ref int swapTimes)
{
//其实根本没必要一个dest.length数组,使得空间复杂度增大
//只需一个int零时变量即可,当前要排序的元素腾出即可
ArrayList destArray = new ArrayList();
destArray.Add(dest[0]);
for(int i = 1; i < dest.Length; i ++)
{
bool ins = false;
for(int j = 0; j <= i - 1; j ++)
{
if(dest[i] < (int)destArray[j])
{
ins = true;
swapTimes ++;
destArray.Insert(j, dest[i]);
break;
}
}
if(! ins)
destArray.Insert(i, dest[i]);
}
for(int i = 0; i < dest.Length; i ++)
{
dest[i] = (int)destArray[i];
}
}
三，shell排序
/// <summary>
/// shell sort
/// </summary>
/// <param name="dest">待排序数组</param>
/// <param name="swapTimes">移动元素次数</param>
public static void ShellSort(ref int[] dest, ref int swapTimes)
{
for(int delta = dest.Length / 2; delta >= 0; delta /= 2)
{
if(delta == 0)
break;
else
{
for(int i = 0; i < delta; i ++)
{
for(int j = i; j < dest.Length; j += delta)
{
int temp = dest[j];
int tmp = j;
while(tmp >= delta && temp < dest[tmp - delta])
{
dest[tmp] = dest[tmp - delta];
swapTimes ++;
tmp -= delta;
}
dest[tmp] = temp;
}
}
}
}
}
四，快速排序
public static void QuickSort(ref int[] dest, int beg, int end, ref int swapTimes)
{
if(beg >= end)
return;
int pivot = (beg + end) / 2;
Swap.Swaper(ref dest[pivot], ref dest[end]);
int pivo = Partition(ref dest, beg, end, ref swapTimes);
QuickSort(ref dest, beg, pivo - 1, ref swapTimes);
QuickSort(ref dest, pivo + 1, end, ref swapTimes);
}
private static int Partition(ref int[] dest, int be, int en, ref int swapTimes)
{
int temp = dest[en];
int b = be;
int e = en;
while(b != e)
{
while(dest[b] < temp && b < e)
b ++;
if(b < e)
{
dest[e] = dest[b];
e --;
swapTimes ++;
}
while(dest[e] > temp && b < e)
{
e --;
}
if(b < e)
{
dest[b] = dest[e];
b ++;
swapTimes ++;
}
}
dest[b] = temp;
return b;
}
五，两路归并排序
/// <summary>
/// 对目标数组进行归并排序
/// 与QuickSort的分治比较，感受递归
/// </summary>
/// <param name="dest">目标数组</param>
/// <param name="tempDest">暂存数组</param>
/// <param name="left">当前部分左位置</param>
/// <param name="right">当前部分右位置</param>
/// <param name="swapTimes">当前部分中间位置</param>
public static void TwoWayMergeSort(int[] dest, int[] tempDest, int left, int right, ref int swapTimes)
{
if(left < right)
{
int mid = (left + right) / 2;
//分割通过递归实现
TwoWayMergeSort(dest, tempDest, left, mid, ref swapTimes);//左一半
TwoWayMergeSort(dest, tempDest, mid + 1, right, ref swapTimes);//右一半
Merge(dest, tempDest, left, right, mid, ref swapTimes);//对左右各半进行归并
}
}
/// <summary>
/// 对当前部分进行归并
/// </summary>
/// <param name="dest"></param>
/// <param name="tempDest"></param>
/// <param name="left"></param>
/// <param name="right"></param>
/// <param name="mid"></param>
/// <param name="swapTimes">逆置位置</param>
private static void Merge(int[] dest, int[] tempDest, int left, int right, int mid, ref int swapTimes)
{
for(int i = left; i <= right; i ++)
tempDest[i] = dest[i];
int index1 = left;
int index2 = mid + 1;
int index = left;//用left很重要，如若是0则会对dest的位置重复赋值
//|-------|--------|
// ^index1 ^index2,体现了归并的妙
while(index1 <= mid && index2 <= right)
{
if(tempDest[index1] <= tempDest[index2])
{
dest[index ++] = tempDest[index1 ++];
}
else
{
dest[index ++] = tempDest[index2 ++];
swapTimes ++;
}
}
while(index2 <= right)
{
dest[index ++] = tempDest[index2 ++];
}
while(index1 <= mid)
{
dest[index ++] = tempDest[index1 ++];
}
}
to be continued。。。
