问题描述:
两种选取key位置的方法完全相同，但是调用一个是函数内调用，另一种是函数外调用，但结果是一个起作用一个不起作用，请问这是为什么？下面上代码。
不起作用的调用函数:
/// <summary>
/// 快速排序
/// </summary>
/// <param name="array">支持IComparable并实现CompareTo方法的类型数组</param>
/// <param name="left">分组的左边界(初始为数组内任意元素)</param>
/// <param name="right">分组的右边界(初始为数组右边界)</param>
/// <param name="tiObj">计时器(默认null，如果从外部传入则需要设置startTime)</param>
/// <param name="start">是否是递归初始趟</param>
/// <returns></returns>
public static string[] quickSort(T[] array, int low, int high, bool start, GCTiming tiObj = null)
{
if (tiObj == null)
{
tiObj = new GCTiming();
tiObj.StartTime();
}
int pivot = low;
if (low < high)
{
while (low < high)
{
while (pivot < high)
{
if (array[pivot].CompareTo(array[high]) <= 0)
{
high--;
}
else
{
array_swap(array, pivot, high);
pivot = high;
break;
}
}
while (low < pivot)
{
if (array[low].CompareTo(array[pivot]) <= 0)
{
low++;
}
else
{
array_swap(array, low, pivot);
pivot = low;
break;
}
}
}
//pivot = array_qsort_partition(array, low, high);
quickSort(array, low, pivot - 1, false, tiObj);
quickSort(array, pivot + 1, high, false, tiObj);
}
if (start)
{
//Thread.Sleep(1000);
int a = 10;
object b;
//for (int i = 0; i < 100000; i++)
//{
// b = (object)a;
//}
tiObj.StopTime();
return new string[] { tiObj.Result().TotalMilliseconds.ToString(), SortUtil<T>.intArrToString(array) };
}
return null;
}
另一个起作用的调用方式：
static void array_swap(T[] array, int i, int j)
{
T temp = array[i];
array[i] = array[j];
array[j] = temp;
}
/**
* @author TIAN
* @brief 快速排序（哨兵筛选部分）
*/
static int array_qsort_partition(T[] array, int low, int hight)
{
int pivot = low;
while (low < hight)
{
while (pivot < hight)
{
if (array[pivot].CompareTo(array[hight]) <= 0)
{
hight--;
}
else
{
array_swap(array, pivot, hight);
pivot = hight;
break;
}
}
while (low < pivot)
{
if (array[low].CompareTo(array[pivot]) <= 0)
{
low++;
}
else
{
array_swap(array, low, pivot);
pivot = low;
break;
}
}
}
return pivot;
}
/**
* @author TIAN
* @brief 快速排序（递归部分）
*/
public static string[] array_qsort(T[] array, int low, int high, bool start, GCTiming tiObj = null)
{
if (tiObj == null)
{
tiObj = new GCTiming();
tiObj.StartTime();
}
if (low < high)
{
int pivot = array_qsort_partition(array, low, high);
array_qsort(array, low, pivot - 1, false, tiObj);
array_qsort(array, pivot + 1, high, false, tiObj);
}
if (start)
{
//Thread.Sleep(1000);
int a = 10;
object b;
//for (int i = 0; i < 100000; i++)
//{
// b = (object)a;
//}
tiObj.StopTime();
return new string[] { tiObj.Result().TotalMilliseconds.ToString(), SortUtil<T>.intArrToString(array) };
}
return null;
}
这两种调用为什么一个起作用另一个不起作用呢？
将主函数中的调用也一并奉上，方便大家复现和调试：
main():
class Program
{
static void Main(string[] args)
{
int orderSize = 20000;
string[] lastBaseCounting = null;
int[] arrFixedSize = getBefroeSortArr();
int[] arrOrderSize = getBefroeSortArr2(orderSize);
Console.WriteLine("Any key to start sort conting...\r\nPress ESC to exit this Program\r\n");
while (Console.ReadKey().Key != ConsoleKey.Escape)
{
printStartInfo("fixedSizeArr", arrFixedSize);
printStartInfo("orderSize", arrOrderSize);
//选择排序
string[] res = SortComponent<int>.selectionSortSimple(getTmpArray(arrOrderSize));
printEndInfo("selectionSortSimple:", fixContingTime(lastBaseCounting, res));
//插入排序
/*//这行会出问题，第一组选择排序的执行时间变成了0
//res = SortComponent<int>.insertSortSimple(getBefroeSortArr2(50000)); */
/*这样取结果就没问题,选择排序的执行时间会打印出来*/
string[] res1 = SortComponent<int>.insertSortSimple(getTmpArray(arrOrderSize));
printEndInfo("insertSortSimple:", fixContingTime(res,res1));
//冒泡排序
string[] res2 = SortComponent<int>.popSort(getTmpArray(arrOrderSize));
printEndInfo("popSort:", fixContingTime(res1, res2));
//鸡尾酒排序(双向冒泡排序)
string[] res3 = SortComponent<int>.cocktailSort(getTmpArray(arrOrderSize));
printEndInfo("cocktailSort", fixContingTime(res2, res3));
string[] res4 = SortComponent<int>.shellSort(getTmpArray(arrOrderSize));
printEndInfo("shellSort", fixContingTime(res3, res4));
string[] res5 = SortComponent<int>.quickSort(getTmpArray(arrOrderSize), 0, orderSize - 1, true);
printEndInfo("quickSort", fixContingTime(res4, res5));
//string[] res5 = SortComponent<int>.array_qsort(getTmpArray(arrOrderSize), 0, orderSize - 1, true);
//printEndInfo("quickSort", fixContingTime(res4, res5));
printEndInfoWithNoArrayRes("selectionSortSimple:", fixContingTime(lastBaseCounting, res));
printEndInfoWithNoArrayRes("insertSortSimple:", fixContingTime(res, res1));
printEndInfoWithNoArrayRes("popSort:", fixContingTime(res1, res2));
printEndInfoWithNoArrayRes("cocktailSort:", fixContingTime(res2, res3));
printEndInfoWithNoArrayRes("shellSort:", fixContingTime(res3, res4));
printEndInfoWithNoArrayRes("quickSort:", fixContingTime(res4, res5));
lastBaseCounting = res;
arrOrderSize = getBefroeSortArr2(orderSize);
}
//Console.WriteLine("Sort program is end\r\nPress any key to exit program...");
//Console.ReadKey();
}
static void PrintArray(string[] array)
{
Console.WriteLine(SortUtil<string>.intArrToString(array));
}
static void printStartInfo(string arrname, int[] array)
{
Console.WriteLine("{0} before sort is:\r\n", arrname);
PrintArray(Array.ConvertAll<int, string>(array, s => s.ToString()));
}
static void printEndInfo(string name, string[] sortRes)
{
Console.WriteLine("after {0} sort:\r\n{2}\r\ntotal time is :{1}ms\r\n\r\n", name, sortRes[0], sortRes[1]);
}
static void printEndInfoWithNoArrayRes(string name, string[] sortRes)
{
Console.WriteLine("{0}\r\ntotal time is :{1}ms\r\n\r\n", name, sortRes[0], sortRes[1]);
}
static int[] getBefroeSortArr()
{
return new int[] { 2, 9, 2, 1, 8, 2, 3, 5, 19, 29, 13, 11, 45 };
//return new int[] { 1, 18, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 };
}
static int[] getBefroeSortArr2(int length = 100)
{
int[] arr = new int[length];
Random rn = new Random();
for (int i = 0; i < length; i++)
{
arr[i] = rn.Next(1, length);
}
return arr;
}
/// <summary>
/// 创建基础排序数列的副本
/// </summary>
/// <param name="arr">样本数列</param>
/// <returns></returns>
static int[] getTmpArray(int[] arr)
{
int[] tmpArr = new int[arr.Length];
arr.CopyTo(tmpArr, 0);
return tmpArr;
}
static string[] fixContingTime(string[] resPre,string[] resCur)
{
if (resPre == null)
{
return resCur;
}
string[] tempResForReturn = new string[2];
resCur.CopyTo(tempResForReturn,0);
double tmpContingTiem = double.Parse(resPre[0]);
tempResForReturn[0] = (double.Parse(resCur[0]) - tmpContingTiem).ToString();
return tempResForReturn;
}
}
class SortUtil<T>
{
public static void swap(T[] array, int i, int min)
{
T temp = array[i];
array[i] = array[min];
array[min] = temp;
}
void swap7(int x, int y)
{
if (x == y)
return;
y = x + y - (x = y);
}
public static string intArrToString(T[] array)
{
return string.Join(",", Array.ConvertAll<T, string>(array, s => s.ToString()));
}
}
算了，我把排序那个类的完整代码也放上来吧：
/// <summary>
/// 选择排序
/// </summary>
/// <typeparam name="T"></typeparam>
class SortComponent<T> where T : IComparable<T>
{
public static string[] selectionSortSimple(T[] array)
{
int n = array.Length;
GCTiming tiObj = new GCTiming();
//Thread.Sleep(1000);
tiObj.StartTime();
Console.WriteLine("选择排序(selectionSort)开始:");
for (int i = 0; i < n; i++)
{
int min = i;
for (int j = i + 1; j < n; j++)
{
if (array[min].CompareTo(array[j]) > 0)
{
min = j;
}
}
SortUtil<T>.swap(array, i, min);
}
tiObj.StopTime();
return new string[] { tiObj.Result().TotalMilliseconds.ToString(), SortUtil<T>.intArrToString(array) };
}
/// <summary>
/// 插入排序
/// 一、插入排序
///特点：stable sort、In-place sort
///最优复杂度：当输入数组就是排好序的时候，复杂度为O(n)，而快速排序在这种情况下会产生O(n^2)的复杂度。
///最差复杂度：当输入数组为倒序时，复杂度为O(n^2)
///插入排序比较适合用于“少量元素的数组”。
/// </summary>
/// <param name="array"></param>
/// <returns></returns>
public static string[] insertSortSimple(T[] array)
{
int n = array.Length;
GCTiming tiOb = new GCTiming();
tiOb.StartTime();
Console.WriteLine("插入排序(insertionSort)开始:");
//默认第一个元素排好序了，所以从第二个开始往排好序的方向比较
for (int i = 1; i < n; i++)
{
//与排好序的方向比较，如果小于前面的就交换后继续比，直到相等或大于后，从刚才的i下标继续往n的方向取元素排序
for (int j = i; j > 0; j--)
{
if (array[j].CompareTo(array[j - 1]) < 0)
{
SortUtil<T>.swap(array, j, j - 1);
}
else//如果下标i指针项大于比较项，则无需再向排好序的方向继续比较，因为前面的都是排好序的
{
break;
}
}
}
tiOb.StopTime();
return new string[] { tiOb.Result().TotalMilliseconds.ToString(), SortUtil<T>.intArrToString(array) };
}
public static string[] popSort(T[] array)
{
int n = array.Length;
bool popflag = true;
GCTiming tiObj = new GCTiming();
tiObj.StartTime();
for (int i = 0; i < n && popflag; i++)
{
popflag = false;
for (int j = 0; j < n - i - 1; j++)
{
if (array[j].CompareTo(array[j + 1]) > 0)
{
SortUtil<T>.swap(array, j, j + 1);
popflag = true;
}
}
}
tiObj.StopTime();
return new string[] { tiObj.Result().TotalMilliseconds.ToString(), SortUtil<T>.intArrToString(array) };
}
public static string[] cocktailSort(T[] array)
{
int n = array.Length;
bool cocktailFlag = true;
GCTiming tiObj = new GCTiming();
tiObj.StartTime();
for (int i = 0; i < n && cocktailFlag; i++)
{
for (int j = 0; j < n - i - 1; j++)
{
//大的往后排
if (array[j].CompareTo(array[j + 1]) > 0)
{
SortUtil<T>.swap(array, j, j + 1);
cocktailFlag = true;
}
}
for (int k = n - (i + 1) - 1; k > i; k--)
{
//小的往前排
if (array[k].CompareTo(array[k - 1]) < 0)
{
SortUtil<T>.swap(array, k, k - 1);
cocktailFlag = true;
}
}
}
tiObj.StopTime();
return new string[] { tiObj.Result().TotalMilliseconds.ToString(), SortUtil<T>.intArrToString(array) };
}
/// <summary>
/// 希尔排序
/// </summary>
/// <param name="array"></param>
/// <returns></returns>
public static string[] shellSort(T[] array)
{
int n = array.Length;
int stepLenth = 1;
GCTiming tiObj = new GCTiming();
tiObj.StartTime();
while (stepLenth < n / 3)
/*目前已知最好的序列: Sedgewick's 序列 (Knuth的学生，Algorithems的作者)的序列: 1, 5, 19, 41, 109, ....
该序列由下面两个表达式交互获得:
1, 19, 109, 505, 2161,….., 9(4k – 2k) + 1, k = 0, 1, 2, 3,…
5, 41, 209, 929, 3905,…..2k+2 (2k+2 – 3 ) + 1, k = 0, 1, 2, 3, …
*/
{
stepLenth = stepLenth * 3 + 1;
}
while (stepLenth >= 1)
{
//从第二个元素开始
for (int i = 1; i < n; i++)
{
//从第i个元素开始，依次次和前面已经排好序的i-h个元素比较，如果小于，则交换
for (int j = i; j >= stepLenth; j -= stepLenth)
{
if (array[j].CompareTo(array[j - stepLenth]) < 0)
{
SortUtil<T>.swap(array, j, j - stepLenth);
}
else//如果大于，则不用继续往前比较了，因为前面的元素已经排好序，比较大的大就是教大的了。
{ break; }
}
}
stepLenth = stepLenth / 3;//步长除以三递减
}
tiObj.StopTime();
return new string[] { tiObj.Result().TotalMilliseconds.ToString(), SortUtil<T>.intArrToString(array) };
}
/// <summary>
/// 快速排序
/// </summary>
/// <param name="array">支持IComparable并实现CompareTo方法的类型数组</param>
/// <param name="left">分组的左边界(初始为数组内任意元素)</param>
/// <param name="right">分组的右边界(初始为数组右边界)</param>
/// <param name="tiObj">计时器(默认null，如果从外部传入则需要设置startTime)</param>
/// <param name="start">是否是递归初始趟</param>
/// <returns></returns>
public static string[] quickSort(T[] array, int low, int high, bool start, GCTiming tiObj = null)
{
if (tiObj == null)
{
tiObj = new GCTiming();
tiObj.StartTime();
}
int pivot = low;
if (low < high)
{
while (low < high)
{
while (pivot < high)
{
if (array[pivot].CompareTo(array[high]) <= 0)
{
high--;
}
else
{
array_swap(array, pivot, high);
pivot = high;
break;
}
}
while (low < pivot)
{
if (array[low].CompareTo(array[pivot]) <= 0)
{
low++;
}
else
{
array_swap(array, low, pivot);
pivot = low;
break;
}
}
}
//pivot = array_qsort_partition(array, low, high);
quickSort(array, low, pivot - 1, false, tiObj);
quickSort(array, pivot + 1, high, false, tiObj);
}
if (start)
{
//Thread.Sleep(1000);
int a = 10;
object b;
//for (int i = 0; i < 100000; i++)
//{
// b = (object)a;
//}
tiObj.StopTime();
return new string[] { tiObj.Result().TotalMilliseconds.ToString(), SortUtil<T>.intArrToString(array) };
}
return null;
}
static void array_swap(T[] array, int i, int j)
{
T temp = array[i];
array[i] = array[j];
array[j] = temp;
}
/**
* @author TIAN
* @brief 快速排序（哨兵筛选部分）
*/
static int array_qsort_partition(T[] array, int low, int hight)
{
int pivot = low;
while (low < hight)
{
while (pivot < hight)
{
if (array[pivot].CompareTo(array[hight]) <= 0)
{
hight--;
}
else
{
array_swap(array, pivot, hight);
pivot = hight;
break;
}
}
while (low < pivot)
{
if (array[low].CompareTo(array[pivot]) <= 0)
{
low++;
}
else
{
array_swap(array, low, pivot);
pivot = low;
break;
}
}
}
return pivot;
}
/**
* @author TIAN
* @brief 快速排序（递归部分）
*/
public static string[] array_qsort(T[] array, int low, int high, bool start, GCTiming tiObj = null)
{
if (tiObj == null)
{
tiObj = new GCTiming();
tiObj.StartTime();
}
if (low < high)
{
int pivot = array_qsort_partition(array, low, high);
array_qsort(array, low, pivot - 1, false, tiObj);
array_qsort(array, pivot + 1, high, false, tiObj);
}
if (start)
{
//Thread.Sleep(1000);
int a = 10;
object b;
//for (int i = 0; i < 100000; i++)
//{
// b = (object)a;
//}
tiObj.StopTime();
return new string[] { tiObj.Result().TotalMilliseconds.ToString(), SortUtil<T>.intArrToString(array) };
}
return null;
}
}
请高手们帮我解答一下吧~