#if 0
#include <stdio.h>
#include <time.h>
void BubbleSort(int k[], int n)
{
int i, j, temp, count1 = 0, count2 = 0;
for (i = 0; i < n - 1; i++)
{
for (j = i + 1; j < n; j++)
{
count1++;
if (k[i] > k[j])
{
{
int i, j, temp, count1 = 0, count2 = 0;
for (i = 0; i < n - 1; i++)
{
for (j = i + 1; j < n; j++)
{
count1++;
if (k[i] > k[j])
{
count2++;
temp = k[i];
k[i] = k[j];
k[j] = temp;
}
}
}
printf("总共进行了%d次比较，进行了%d次移动", count1, count2);
}
temp = k[i];
k[i] = k[j];
k[j] = temp;
}
}
}
printf("总共进行了%d次比较，进行了%d次移动", count1, count2);
}
int main()
{
int i, a[10] = { 4,0,0,1,1,6,4,3,9,3 };
double start, finish;
start = clock();
BubbleSort(a, 10);
{
int i, a[10] = { 4,0,0,1,1,6,4,3,9,3 };
double start, finish;
start = clock();
BubbleSort(a, 10);
printf("排序后的结果为：
");
for (i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
finish = clock();
printf(" 所耗费的时间为: %f ms ", (finish - start));
return 0;
}
{
printf("%d ", a[i]);
}
finish = clock();
printf(" 所耗费的时间为: %f ms ", (finish - start));
return 0;
}
#elif 0
/*冒泡排序*/
#include <stdio.h>
#include <time.h>
/*冒泡排序*/
#include <stdio.h>
#include <time.h>
void BubbleSort(int k[], int n)
{
int i, j, temp, count1 = 0, count2 = 0, flag;
flag = 1;
for (i = 0; i < n - 1 && flag; i++)
{
flag = 0;
for (j = n - 1; j > i; j--)
{
count1++;
if (k[j - 1] > k[j])
{
count2++;
temp = k[j - 1];
k[j - 1] = k[j];
k[j] = temp;
flag = 1;
}
}
}
printf("总共进行了%d次比较，进行了%d次移动", count1, count2);
}
{
int i, j, temp, count1 = 0, count2 = 0, flag;
flag = 1;
for (i = 0; i < n - 1 && flag; i++)
{
flag = 0;
for (j = n - 1; j > i; j--)
{
count1++;
if (k[j - 1] > k[j])
{
count2++;
temp = k[j - 1];
k[j - 1] = k[j];
k[j] = temp;
flag = 1;
}
}
}
printf("总共进行了%d次比较，进行了%d次移动", count1, count2);
}
int main()
{
int i, a[10] = { 4,0,0,1,1,6,4,3,9,3 };
double start, finish;
start = clock();
BubbleSort(a, 10);
{
int i, a[10] = { 4,0,0,1,1,6,4,3,9,3 };
double start, finish;
start = clock();
BubbleSort(a, 10);
printf("排序后的结果为：
");
for (i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
finish = clock();
printf(" 所耗费的时间为: %f ms ", (finish - start));
return 0;
}
{
printf("%d ", a[i]);
}
finish = clock();
printf(" 所耗费的时间为: %f ms ", (finish - start));
return 0;
}
#elif 0
/*选择排序*/
#include <stdio.h>
#include <time.h>
/*选择排序*/
#include <stdio.h>
#include <time.h>
void SelectSort(int k[], int n)
{
int i, j, min, count1 = 0, count2 = 0, temp;
for (i = 0; i < n - 1; i++)
{
min = i;
for (j = i + 1; j < n; j++)
{
count1++;
if (k[j] < k[min])
{
min = j;
}
}
if (min != i)
{
count2++;;
temp = k[min];
k[min] = k[i];
k[i] = temp;
}
}
printf("总共进行了%d次比较，进行了%d次移动", count1, count2);
}
{
int i, j, min, count1 = 0, count2 = 0, temp;
for (i = 0; i < n - 1; i++)
{
min = i;
for (j = i + 1; j < n; j++)
{
count1++;
if (k[j] < k[min])
{
min = j;
}
}
if (min != i)
{
count2++;;
temp = k[min];
k[min] = k[i];
k[i] = temp;
}
}
printf("总共进行了%d次比较，进行了%d次移动", count1, count2);
}
int main()
{
int i, a[10] = { 4,0,0,1,1,6,4,3,9,3 };
double start, finish;
start = clock();
SelectSort(a, 10);
{
int i, a[10] = { 4,0,0,1,1,6,4,3,9,3 };
double start, finish;
start = clock();
SelectSort(a, 10);
printf("排序后的结果为：
");
for (i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
finish = clock();
printf(" 所耗费的时间为: %f ms ", (finish - start));
return 0;
}
{
printf("%d ", a[i]);
}
finish = clock();
printf(" 所耗费的时间为: %f ms ", (finish - start));
return 0;
}
#elif 0
/*直接插入排序*/
#include <stdio.h>
#include <time.h>
/*直接插入排序*/
#include <stdio.h>
#include <time.h>
void InsertSort(int k[], int n)
{
int i, j, min, count1 = 0, count2 = 0, temp;
for (i = 1; i < n; i++)
{
if (k[i] < k[i - 1])
{
count1++;
temp = k[i];
// k[i] = k[i-1];
for (j = i - 1; k[j] > temp && j >= 0; j--) //此处修改i前面的数，重新排序。
{
count2++;
k[j + 1] = k[j];
}
{
int i, j, min, count1 = 0, count2 = 0, temp;
for (i = 1; i < n; i++)
{
if (k[i] < k[i - 1])
{
count1++;
temp = k[i];
// k[i] = k[i-1];
for (j = i - 1; k[j] > temp && j >= 0; j--) //此处修改i前面的数，重新排序。
{
count2++;
k[j + 1] = k[j];
}
k[j + 1] = temp;
}
}
printf("总共进行了%d次比较，进行了%d次移动", count1, count2);
}
}
}
printf("总共进行了%d次比较，进行了%d次移动", count1, count2);
}
int main()
{
int i, a[10] = { 4,0,0,1,1,6,4,3,9,3 };
double start, finish;
start = clock();
InsertSort(a, 10);
{
int i, a[10] = { 4,0,0,1,1,6,4,3,9,3 };
double start, finish;
start = clock();
InsertSort(a, 10);
printf("排序后的结果为：
");
for (i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
finish = clock();
printf(" 所耗费的时间为: %f ms ", (finish - start));
return 0;
}
{
printf("%d ", a[i]);
}
finish = clock();
printf(" 所耗费的时间为: %f ms ", (finish - start));
return 0;
}
#elif 0
/*希尔排序*/
#include <stdio.h>
#include <time.h>
/*希尔排序*/
#include <stdio.h>
#include <time.h>
void InsertSort(int k[], int n)
{
int i, j, min, count1 = 0, count2 = 0, temp;
int gap = n;
{
int i, j, min, count1 = 0, count2 = 0, temp;
int gap = n;
do
{
gap = gap / 3 + 1; //希尔排序，设置排序插入间隔，很精髓，复杂度从O(n^2)降到了O(n*logn)!!
for (i = gap; i < n; i++)
{
if (k[i] < k[i - gap])
{
count1++;
temp = k[i];
// k[i] = k[i-1];
for (j = i - gap; k[j] > temp && j >= 0; j -= gap) //此处修改i前面的数，重新排序。
{
count2++;
k[j + gap] = k[j];
}
{
gap = gap / 3 + 1; //希尔排序，设置排序插入间隔，很精髓，复杂度从O(n^2)降到了O(n*logn)!!
for (i = gap; i < n; i++)
{
if (k[i] < k[i - gap])
{
count1++;
temp = k[i];
// k[i] = k[i-1];
for (j = i - gap; k[j] > temp && j >= 0; j -= gap) //此处修改i前面的数，重新排序。
{
count2++;
k[j + gap] = k[j];
}
k[j + gap] = temp;
}
}
} while (gap > 1);
}
}
} while (gap > 1);
printf("总共进行了%d次比较，进行了%d次移动", count1, count2);
}
}
int main()
{
int i, a[10] = { 4,0,0,1,1,6,4,3,9,3 };
double start, finish;
start = clock();
InsertSort(a, 10);
{
int i, a[10] = { 4,0,0,1,1,6,4,3,9,3 };
double start, finish;
start = clock();
InsertSort(a, 10);
printf("排序后的结果为：
");
for (i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
finish = clock();
printf(" 所耗费的时间为: %f ms ", (finish - start));
return 0;
}
{
printf("%d ", a[i]);
}
finish = clock();
printf(" 所耗费的时间为: %f ms ", (finish - start));
return 0;
}
#elif 0
/*堆排序，大顶堆*/
#include <stdio.h>
#include <time.h>
/*堆排序，大顶堆*/
#include <stdio.h>
#include <time.h>
void swap(int k[], int &i, int &j)
{
int temp;
temp = k[i];
k[i] = k[j];
k[j] = temp;
}
{
int temp;
temp = k[i];
k[i] = k[j];
k[j] = temp;
}
void HeapAdjust(int k[], int s, int n)
{
int i, temp;
temp = k[s];
for (i = 2 * s; i <= n; i *= 2)
{
if (i < n && k[i] < k[i + 1])
{
i++;
}
if (temp >= k[i])
{
break;
}
k[s] = k[i];
s = i;
}
k[s] = temp;
}
{
int i, temp;
temp = k[s];
for (i = 2 * s; i <= n; i *= 2)
{
if (i < n && k[i] < k[i + 1])
{
i++;
}
if (temp >= k[i])
{
break;
}
k[s] = k[i];
s = i;
}
k[s] = temp;
}
void HeapSort(int k[], int n)
{
int i;
for (i = n / 2; i > 0; i--)
{
HeapAdjust(k, i, n);
}
for (i = n; i > 1; i--)
{
swap(k, 1, i);
HeapAdjust(k, 1, i - 1);
}
}
{
int i;
for (i = n / 2; i > 0; i--)
{
HeapAdjust(k, i, n);
}
for (i = n; i > 1; i--)
{
swap(k, 1, i);
HeapAdjust(k, 1, i - 1);
}
}
int main()
{
int i, a[10] = { -1,5,2,6,0,3,9,1,7,4 };
double start, finish;
start = clock();
HeapSort(a, 9);
{
int i, a[10] = { -1,5,2,6,0,3,9,1,7,4 };
double start, finish;
start = clock();
HeapSort(a, 9);
printf("排序后的结果为：
");
for (i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
finish = clock();
printf(" 所耗费的时间为: %f ms ", (finish - start));
return 0;
}
{
printf("%d ", a[i]);
}
finish = clock();
printf(" 所耗费的时间为: %f ms ", (finish - start));
return 0;
}
#elif 0
/*归并排序*/
#include <stdio.h>
#include <time.h>
#define MAXSIZE 10
/*归并排序*/
#include <stdio.h>
#include <time.h>
#define MAXSIZE 10
//实现归并，并把最后的结果存放在 list1 里面。
void merging(int *list1, int list1_size, int *list2, int list2_size)
{
int i, j, k, m;
int temp[MAXSIZE];
i = j = k = 0;
void merging(int *list1, int list1_size, int *list2, int list2_size)
{
int i, j, k, m;
int temp[MAXSIZE];
i = j = k = 0;
while (i < list1_size && j < list2_size)
{
if (list1[i] < list2[j])
{
temp[k++] = list1[i++];
}
else
{
temp[k++] = list2[j++];
}
}
{
if (list1[i] < list2[j])
{
temp[k++] = list1[i++];
}
else
{
temp[k++] = list2[j++];
}
}
while (i < list1_size)
{
temp[k++] = list1[i++];
}
{
temp[k++] = list1[i++];
}
while (j < list2_size)
{
temp[k++] = list2[j++];
}
{
temp[k++] = list2[j++];
}
for (m = 0; m < list1_size + list2_size; m++)
{
list1[m] = temp[m];
}
}
{
list1[m] = temp[m];
}
}
void MergeSort(int k[], int n)
{
if (n > 1)
{
int *list1 = k;
int list1_size = n / 2;
int *list2 = k + n / 2;
int list2_size = n - list1_size;
{
if (n > 1)
{
int *list1 = k;
int list1_size = n / 2;
int *list2 = k + n / 2;
int list2_size = n - list1_size;
MergeSort(list1, list1_size);
MergeSort(list2, list2_size);
MergeSort(list2, list2_size);
merging(list1, list1_size, list2, list2_size);
}
}
}
}
int main()
{
int i, a[10] = { 5,2,6,0,3,9,1,7,4,8 };
double start, finish;
start = clock();
MergeSort(a, 10);
{
int i, a[10] = { 5,2,6,0,3,9,1,7,4,8 };
double start, finish;
start = clock();
MergeSort(a, 10);
printf("排序后的结果为：
");
for (i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
finish = clock();
printf(" 所耗费的时间为: %f ms ", (finish - start));
return 0;
}
{
printf("%d ", a[i]);
}
finish = clock();
printf(" 所耗费的时间为: %f ms ", (finish - start));
return 0;
}
#elif 0
/*归并排序 迭代实现*/
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define MAXSIZE 10
/*归并排序 迭代实现*/
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define MAXSIZE 10
void MergeSort(int k[], int n)
{
int i, left_min, left_max, right_min, right_max;
int *temp = (int *)malloc(n * sizeof(int));
{
int i, left_min, left_max, right_min, right_max;
int *temp = (int *)malloc(n * sizeof(int));
for (i = 1; i < n; i *= 2) //此处i为步长
{
for (left_min = 0; left_min < n - i; left_min = right_max)
{
right_min = left_max = left_min + i;
right_max = left_max + i;
{
for (left_min = 0; left_min < n - i; left_min = right_max)
{
right_min = left_max = left_min + i;
right_max = left_max + i;
if (right_max > n)
{
right_max = n;
}
int next = 0;
{
right_max = n;
}
int next = 0;
while (left_min < left_max && right_min < right_max)
{
if (k[left_min] < k[right_min])
temp[next++] = k[left_min++];
else
temp[next++] = k[right_min++];
}
{
if (k[left_min] < k[right_min])
temp[next++] = k[left_min++];
else
temp[next++] = k[right_min++];
}
while (left_min < left_max)
{
temp[next++] = k[left_min++];
}
{
temp[next++] = k[left_min++];
}
while (next > 0)
{
k[--right_min] = temp[--next];
}
}
}
{
k[--right_min] = temp[--next];
}
}
}
}
int main()
{
int i, a[10] = { 5,2,6,0,3,9,1,7,4,8 };
double start, finish;
start = clock();
MergeSort(a, 10);
{
int i, a[10] = { 5,2,6,0,3,9,1,7,4,8 };
double start, finish;
start = clock();
MergeSort(a, 10);
printf("排序后的结果为：
");
for (i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
finish = clock();
printf(" 所耗费的时间为: %f ms ", (finish - start));
return 0;
}
{
printf("%d ", a[i]);
}
finish = clock();
printf(" 所耗费的时间为: %f ms ", (finish - start));
return 0;
}
#elif 0
/*快速排序*/
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define MAXSIZE 10
/*快速排序*/
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define MAXSIZE 10
void swap(int k[], int &low, int &high)
{
int temp;
temp = k[low];
k[low] = k[high];
k[high] = temp;
}
{
int temp;
temp = k[low];
k[low] = k[high];
k[high] = temp;
}
int Partition(int k[], int low, int high)
{
int point;
point = k[low];
while (low < high)
{
while (low < high && k[high] >= point)
{
high--;
}
swap(k, low, high);
{
int point;
point = k[low];
while (low < high)
{
while (low < high && k[high] >= point)
{
high--;
}
swap(k, low, high);
while (low < high && k[low] <= point)
{
low++;
}
swap(k, low, high);
}
return point;
}
{
low++;
}
swap(k, low, high);
}
return point;
}
void QSort(int k[], int low, int high)
{
int point;
if (low < high)
{
point = Partition(k, low, high);
{
int point;
if (low < high)
{
point = Partition(k, low, high);
QSort(k, low, point - 1);
QSort(k, point + 1, high);
}
}
QSort(k, point + 1, high);
}
}
void QuickSort(int k[], int n)
{
QSort(k, 0, n - 1);
}
{
QSort(k, 0, n - 1);
}
int main()
{
int i, a[10] = { 5,2,6,0,3,9,1,7,4,8 };
double start, finish;
start = clock();
QuickSort(a, 10);
{
int i, a[10] = { 5,2,6,0,3,9,1,7,4,8 };
double start, finish;
start = clock();
QuickSort(a, 10);
printf("排序后的结果为：
");
for (i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
finish = clock();
printf(" 所耗费的时间为: %f ms ", (finish - start));
return 0;
}
{
printf("%d ", a[i]);
}
finish = clock();
printf(" 所耗费的时间为: %f ms ", (finish - start));
return 0;
}
#elif 0
/*快速排序 优化后的算法 1 */
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define MAXSIZE 10
/*快速排序 优化后的算法 1 */
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define MAXSIZE 10
void swap(int k[], int &low, int &high)
{
int temp;
temp = k[low];
k[low] = k[high];
k[high] = temp;
}
{
int temp;
temp = k[low];
k[low] = k[high];
k[high] = temp;
}
int Partition(int k[], int low, int high)
{
int point;
{
int point;
int m = low + (high - low) / 2;
if (k[low] > k[high])
swap(k, low, high);
if (k[m] > k[high])
swap(k, m, high);
if (k[m] > k[low])
swap(k, m, low);
if (k[low] > k[high])
swap(k, low, high);
if (k[m] > k[high])
swap(k, m, high);
if (k[m] > k[low])
swap(k, m, low);
point = k[low];
while (low < high)
{
while (low < high && k[high] >= point)
{
high--;
}
swap(k, low, high);
while (low < high)
{
while (low < high && k[high] >= point)
{
high--;
}
swap(k, low, high);
while (low < high && k[low] <= point)
{
low++;
}
swap(k, low, high);
}
return point;
}
{
low++;
}
swap(k, low, high);
}
return point;
}
void QSort(int k[], int low, int high)
{
int point;
if (low < high)
{
point = Partition(k, low, high);
{
int point;
if (low < high)
{
point = Partition(k, low, high);
QSort(k, low, point - 1);
QSort(k, point + 1, high);
}
}
QSort(k, point + 1, high);
}
}
void QuickSort(int k[], int n)
{
QSort(k, 0, n - 1);
}
{
QSort(k, 0, n - 1);
}
int main()
{
int i, a[10] = { 5,2,6,0,3,9,1,7,4,8 };
double start, finish;
start = clock();
QuickSort(a, 10);
{
int i, a[10] = { 5,2,6,0,3,9,1,7,4,8 };
double start, finish;
start = clock();
QuickSort(a, 10);
printf("排序后的结果为：
");
for (i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
finish = clock();
printf(" 所耗费的时间为: %f ms ", (finish - start));
return 0;
}
{
printf("%d ", a[i]);
}
finish = clock();
printf(" 所耗费的时间为: %f ms ", (finish - start));
return 0;
}
#elif 0
/*快速排序 优化后的算法 2 */
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define MAXSIZE 10
/*快速排序 优化后的算法 2 */
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define MAXSIZE 10
void swap(int k[], int &low, int &high)
{
int temp;
temp = k[low];
k[low] = k[high];
k[high] = temp;
}
{
int temp;
temp = k[low];
k[low] = k[high];
k[high] = temp;
}
int Partition(int k[], int low, int high)
{
int point;
{
int point;
int m = low + (high - low) / 2;
if (k[low] > k[high])
swap(k, low, high);
if (k[m] > k[high])
swap(k, m, high);
if (k[m] > k[low])
swap(k, m, low);
if (k[low] > k[high])
swap(k, low, high);
if (k[m] > k[high])
swap(k, m, high);
if (k[m] > k[low])
swap(k, m, low);
point = k[low];
while (low < high)
{
while (low < high && k[high] >= point)
{
high--;
}
k[low] = k[high];
while (low < high)
{
while (low < high && k[high] >= point)
{
high--;
}
k[low] = k[high];
while (low < high && k[low] <= point)
{
low++;
}
k[high] = k[low];
}
k[low] = point;
return point;
}
{
low++;
}
k[high] = k[low];
}
k[low] = point;
return point;
}
void QSort(int k[], int low, int high)
{
int point;
if (low < high)
{
point = Partition(k, low, high);
{
int point;
if (low < high)
{
point = Partition(k, low, high);
QSort(k, low, point - 1);
QSort(k, point + 1, high);
}
}
QSort(k, point + 1, high);
}
}
void QuickSort(int k[], int n)
{
QSort(k, 0, n - 1);
}
{
QSort(k, 0, n - 1);
}
int main()
{
int i, a[10] = { 5,2,6,0,3,9,1,7,4,8 };
double start, finish;
start = clock();
QuickSort(a, 10);
{
int i, a[10] = { 5,2,6,0,3,9,1,7,4,8 };
double start, finish;
start = clock();
QuickSort(a, 10);
printf("排序后的结果为：
");
for (i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
finish = clock();
printf(" 所耗费的时间为: %f ms ", (finish - start));
return 0;
}
{
printf("%d ", a[i]);
}
finish = clock();
printf(" 所耗费的时间为: %f ms ", (finish - start));
return 0;
}
#elif 0
/*快速排序 优化后的算法 3 小数组 */
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define MAX_LENGTH_INSERT_SORT 7
/*快速排序 优化后的算法 3 小数组 */
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define MAX_LENGTH_INSERT_SORT 7
void ISort(int k[], int n)
{
int i, j, min, temp;
for (i = 1; i < n; i++)
{
if (k[i] < k[i - 1])
{
temp = k[i];
// k[i] = k[i-1];
for (j = i - 1; k[j] > temp && j >= 0; j--) //此处修改i前面的数，重新排序。
{
k[j + 1] = k[j];
}
{
int i, j, min, temp;
for (i = 1; i < n; i++)
{
if (k[i] < k[i - 1])
{
temp = k[i];
// k[i] = k[i-1];
for (j = i - 1; k[j] > temp && j >= 0; j--) //此处修改i前面的数，重新排序。
{
k[j + 1] = k[j];
}
k[j + 1] = temp;
}
}
}
}
}
}
void InsertSort(int k[], int low, int high)
{
ISort(k + low, high - low + 1);
}
{
ISort(k + low, high - low + 1);
}
void swap(int k[], int &low, int &high)
{
int temp;
temp = k[low];
k[low] = k[high];
k[high] = temp;
}
{
int temp;
temp = k[low];
k[low] = k[high];
k[high] = temp;
}
int Partition(int k[], int low, int high)
{
int point;
{
int point;
int m = low + (high - low) / 2;
if (k[low] > k[high])
swap(k, low, high);
if (k[m] > k[high])
swap(k, m, high);
if (k[m] > k[low])
swap(k, m, low);
if (k[low] > k[high])
swap(k, low, high);
if (k[m] > k[high])
swap(k, m, high);
if (k[m] > k[low])
swap(k, m, low);
point = k[low];
while (low < high)
{
while (low < high && k[high] >= point)
{
high--;
}
k[low] = k[high];
while (low < high)
{
while (low < high && k[high] >= point)
{
high--;
}
k[low] = k[high];
while (low < high && k[low] <= point)
{
low++;
}
k[high] = k[low];
}
k[low] = point;
return point;
}
{
low++;
}
k[high] = k[low];
}
k[low] = point;
return point;
}
void QSort(int k[], int low, int high)
{
int point;
if (high - low > MAX_LENGTH_INSERT_SORT)
{
point = Partition(k, low, high);
QSort(k, low, point - 1);
QSort(k, point + 1, high);
}
else
InsertSort(k, low, high);
}
{
int point;
if (high - low > MAX_LENGTH_INSERT_SORT)
{
point = Partition(k, low, high);
QSort(k, low, point - 1);
QSort(k, point + 1, high);
}
else
InsertSort(k, low, high);
}
void QuickSort(int k[], int n)
{
QSort(k, 0, n - 1);
}
{
QSort(k, 0, n - 1);
}
int main()
{
int i, a[10] = { 5,2,6,0,3,9,1,7,4,8 };
double start, finish;
start = clock();
QuickSort(a, 10);
{
int i, a[10] = { 5,2,6,0,3,9,1,7,4,8 };
double start, finish;
start = clock();
QuickSort(a, 10);
printf("排序后的结果为：
");
for (i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
finish = clock();
printf(" 所耗费的时间为: %f ms ", (finish - start));
return 0;
}
{
printf("%d ", a[i]);
}
finish = clock();
printf(" 所耗费的时间为: %f ms ", (finish - start));
return 0;
}
#elif 1
/*快速排序 优化后的算法 4 优化递归操作（尾递归） */
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define MAX_LENGTH_INSERT_SORT 7
/*快速排序 优化后的算法 4 优化递归操作（尾递归） */
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define MAX_LENGTH_INSERT_SORT 7
void ISort(int k[], int n)
{
int i, j, min, temp;
for (i = 1; i < n; i++)
{
if (k[i] < k[i - 1])
{
temp = k[i];
// k[i] = k[i-1];
for (j = i - 1; k[j] > temp && j >= 0; j--) //此处修改i前面的数，重新排序。
{
k[j + 1] = k[j];
}
{
int i, j, min, temp;
for (i = 1; i < n; i++)
{
if (k[i] < k[i - 1])
{
temp = k[i];
// k[i] = k[i-1];
for (j = i - 1; k[j] > temp && j >= 0; j--) //此处修改i前面的数，重新排序。
{
k[j + 1] = k[j];
}
k[j + 1] = temp;
}
}
}
}
}
}
void InsertSort(int k[], int low, int high)
{
ISort(k + low, high - low + 1);
}
{
ISort(k + low, high - low + 1);
}
void swap(int k[], int &low, int &high)
{
int temp;
temp = k[low];
k[low] = k[high];
k[high] = temp;
}
{
int temp;
temp = k[low];
k[low] = k[high];
k[high] = temp;
}
int Partition(int k[], int low, int high)
{
int point;
{
int point;
int m = low + (high - low) / 2;
if (k[low] > k[high])
swap(k, low, high);
if (k[m] > k[high])
swap(k, m, high);
if (k[m] > k[low])
swap(k, m, low);
if (k[low] > k[high])
swap(k, low, high);
if (k[m] > k[high])
swap(k, m, high);
if (k[m] > k[low])
swap(k, m, low);
point = k[low];
while (low < high)
{
while (low < high && k[high] >= point)
{
high--;
}
k[low] = k[high];
while (low < high)
{
while (low < high && k[high] >= point)
{
high--;
}
k[low] = k[high];
while (low < high && k[low] <= point)
{
low++;
}
k[high] = k[low];
}
k[low] = point;
return point;
}
{
low++;
}
k[high] = k[low];
}
k[low] = point;
return point;
}
void QSort(int k[], int low, int high)
{
int point;
if (high - low > MAX_LENGTH_INSERT_SORT)
{
while (low < high)
{
point = Partition(k, low, high);
if (point - low < high - point)
{
QSort(k, low, point - 1);
//QSort(k, point + 1, high);
low = point + 1; //尾递归
}
else
{
QSort(k, point+1, high);
//QSort(k, point + 1, high);
high = point - 1; //尾递归
}
}
}
else
InsertSort(k, low, high);
}
{
int point;
if (high - low > MAX_LENGTH_INSERT_SORT)
{
while (low < high)
{
point = Partition(k, low, high);
if (point - low < high - point)
{
QSort(k, low, point - 1);
//QSort(k, point + 1, high);
low = point + 1; //尾递归
}
else
{
QSort(k, point+1, high);
//QSort(k, point + 1, high);
high = point - 1; //尾递归
}
}
}
else
InsertSort(k, low, high);
}
void QuickSort(int k[], int n)
{
QSort(k, 0, n - 1);
}
{
QSort(k, 0, n - 1);
}
int main()
{
int i, a[10] = { 5,2,6,0,3,9,1,7,4,8 };
double start, finish;
start = clock();
QuickSort(a, 10);
{
int i, a[10] = { 5,2,6,0,3,9,1,7,4,8 };
double start, finish;
start = clock();
QuickSort(a, 10);
printf("排序后的结果为：
");
for (i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
finish = clock();
printf(" 所耗费的时间为: %f ms ", (finish - start));
return 0;
}
{
printf("%d ", a[i]);
}
finish = clock();
printf(" 所耗费的时间为: %f ms ", (finish - start));
return 0;
}
#endif