[DS][C#]排序算法若干

王朝c#·作者佚名  2006-01-10
窄屏简体版  字體: |||超大  

工作之余,实现排序算法若干如下:

一,冒泡排序

/// <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。。。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航