|
|
一、/*冒泡排序*/
|
|
|
平均时间复杂度:0(n^2)
|
|
|
运行时间:1000随机数：时间为0.003s
|
|
|
1万随机数：时间为0.57s
|
|
|
10万随机数：时间为40.224s
|
|
|
void BubbleSort(int arr[], int length)
|
|
|
{
|
|
|
for (int i = 0; i < length; i++)
|
|
|
{
|
|
|
for (int j = 0; j < length - i - 1; j++)
|
|
|
{
|
|
|
if (arr[j] > arr[j + 1])
|
|
|
{
|
|
|
int temp;
|
|
|
temp = arr[j + 1];
|
|
|
arr[j + 1] = arr[j];
|
|
|
arr[j] = temp;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
二、/* 选择排序 */
|
|
|
平均时间复杂度:0(n^2)
|
|
|
运行时间:1000随机数：时间为：0.004s
|
|
|
1万随机数：时间为：0.225s
|
|
|
10万随机数：时间为：34.125s
|
|
|
void SelectionSort(int arr[], int length)
|
|
|
{
|
|
|
int index, temp;
|
|
|
for (int i = 0; i < length; i++)
|
|
|
{
|
|
|
index = i;
|
|
|
for (int j = i + 1; j < length; j++)
|
|
|
{
|
|
|
if (arr[j] < arr[index])
|
|
|
index = j;
|
|
|
}
|
|
|
if (index != i)
|
|
|
{
|
|
|
temp = arr[i];
|
|
|
arr[i] = arr[index];
|
|
|
arr[index] = temp;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
三、/*插入排序*/
|
|
|
平均时间复杂度：0(n^2)
|
|
|
运行时间:1000个随机数：时间为：0.003s
|
|
|
1万个随机数：时间为：0.195s
|
|
|
10万个随机数：时间为：21.671s
|
|
|
void InsertSort(int arr[], int length)
|
|
|
{
|
|
|
for (int i = 1; i < length; i++)
|
|
|
{
|
|
|
int j;
|
|
|
if (arr[i] < arr[i - 1])
|
|
|
{
|
|
|
int temp = arr[i];
|
|
|
for (j = i - 1; j >= 0 && temp < arr[j]; j--)
|
|
|
{
|
|
|
arr[j + 1] = arr[j];
|
|
|
}
|
|
|
arr[j + 1] = temp;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
四、/*归并排序*/
|
|
|
平均时间复杂度：0(n*log2n)
|
|
|
运行时间:1000随机数：时间为0.001s
|
|
|
1万随机数：时间为0.049s
|
|
|
10万随机数：时间为6.908s
|
|
|
void MergeSort(int arr[], int start, int end, int * temp)
|
|
|
{
|
|
|
if (start >= end)
|
|
|
return;
|
|
|
int mid = (start + end) / 2;
|
|
|
MergeSort(arr, start, mid, temp);
|
|
|
MergeSort(arr, mid + 1, end, temp);
|
|
|
int length = 0;
|
|
|
int i_start = start;
|
|
|
int i_end = mid;
|
|
|
int j_start = mid + 1;
|
|
|
int j_end = end;
|
|
|
while (i_start <= i_end && j_start <= j_end)
|
|
|
{
|
|
|
if (arr[i_start] < arr[j_start])
|
|
|
{
|
|
|
temp[length] = arr[i_start];
|
|
|
length++;
|
|
|
i_start++;
|
|
|
}
|
|
|
else
|
|
|
{
|
|
|
temp[length] = arr[j_start];
|
|
|
length++;
|
|
|
j_start++;
|
|
|
}
|
|
|
}
|
|
|
while (i_start <= i_end)
|
|
|
{
|
|
|
temp[length] = arr[i_start];
|
|
|
i_start++;
|
|
|
length++;
|
|
|
}
|
|
|
while (j_start <= j_end)
|
|
|
{
|
|
|
temp[length] = arr[j_start];
|
|
|
length++;
|
|
|
j_start++;
|
|
|
}
|
|
|
for (int i = 0; i < length; i++)
|
|
|
{
|
|
|
arr[start + i] = temp[i];
|
|
|
}
|
|
|
}
|
|
|
五、/*快速排序*/
|
|
|
平均时间复杂度：0(n*log2n)
|
|
|
运行速度:1000随机数：时间为0.001s
|
|
|
1万随机数：时间为0.005s
|
|
|
10万随机数：时间为0.139s
|
|
|
void QuickSort(int arr[], int start, int end)
|
|
|
{
|
|
|
if (start >= end)
|
|
|
return;
|
|
|
int i = start;
|
|
|
int j = end;
|
|
|
int baseval = arr[start];
|
|
|
while (i < j)
|
|
|
{
|
|
|
while (i < j && arr[j] >= baseval)
|
|
|
{
|
|
|
j--;
|
|
|
}
|
|
|
if (i < j)
|
|
|
{
|
|
|
arr[i] = arr[j];
|
|
|
i++;
|
|
|
}
|
|
|
while (i < j && arr[i] < baseval)
|
|
|
{
|
|
|
i++;
|
|
|
}
|
|
|
if (i < j)
|
|
|
{
|
|
|
arr[j] = arr[i];
|
|
|
j--;
|
|
|
}
|
|
|
}
|
|
|
arr[i] = baseval;
|
|
|
QuickSort(arr, start, i - 1);
|
|
|
QuickSort(arr, i + 1, end);
|
|
|
}
|
|
|
六、/*希尔排序*/
|
|
|
平均时间复杂度：0(n^1.3)
|
|
|
运行速度:1000随机数：时间为：0.001s
|
|
|
1万随机数：时间为：0.051s
|
|
|
10万随机数：时间为：5.253s
|
|
|
void ShellSort(int arr[], int length)
|
|
|
{
|
|
|
int increasement = length;
|
|
|
int i, j, k;
|
|
|
do
|
|
|
{
|
|
|
increasement = increasement / 3 + 1;
|
|
|
for (i = 0; i < increasement; i++)
|
|
|
{
|
|
|
for (j = i + increasement; j < length; j += increasement)
|
|
|
{
|
|
|
if (arr[j] < arr[j - increasement])
|
|
|
{
|
|
|
int temp = arr[j];
|
|
|
for (k = j - increasement; k >= 0 && temp < arr[k]; k -= increasement)
|
|
|
{
|
|
|
arr[k + increasement] = arr[k];
|
|
|
}
|
|
|
arr[k + increasement] = temp;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
} while (increasement > 1);
|
|
|
}
|
|
|
比较总结：
|
|
|
1.对1000个随机数进行排序：
|
|
|
六种排序算法的所需时间均接近0.001s，速度都很快。
|
|
|
2.对1万个随机数进行排序：
|
|
|
快速0.005s < 希尔0.051s < 归并0.049s < 插入0.195s < 选择0.225s < 冒泡0.57s
|
|
|
很明显，快速排序法最快，冒泡排序法最慢。
|
|
|
3.对10万个随机数进行排序：
|
|
|
快速0.139s < 希尔5.253s < 归并6.908s < 插入21.671s < 选择34.125s < 冒泡40.224s
|
|
|
快速排序法最快，冒泡排序法最慢。
|
|
|
4.对100万个随机数进行排序：
|
|
|
快速10.624s，其余算法时间未知，几分钟内排序无法完成。
|
|
|
|
