- //
- // main.c
- // SeletSortArray
- //
- // Created by apple on 15-4-23.
- // Copyright (c) 2015年 __MyCompanyName__. All rights reserved.
- //
- #include <stdio.h>
- #include <time.h>
- #include <stdlib.h>
- #define N 100000
- /* 函数原型 */
- void SeletSort(int v[], int n);
- void SortIntArray(int v[], int n);
- void Merge(int v[], int arr1[], int n1, int arr2[], int n2);
- int *CopySubArray(int v[], int start, int n);
- void quicksort(int v[], int n);
- int partition(int v[], int n);
- void InsertSort(int v[], int n);
- int main(int argc, const char * argv[])
- {
- int v[N];
- double start, end;
- printf("This program sorted a array.\\n");
- /* 初始化数组 */
- for (int i = 0; i < N; i++) {
- v[i] = N - i;
- }
- start = clock();
- /* 把这里的函数换一下就可以对不同算法的时间进行测试 */
- InsertSort(v, N);
- end = clock();
- printf("The sorting time is %lf seconds\\n", (end - start)/CLOCKS_PER_SEC);
- /*
- for (int i = 0; i < N; i++) {
- printf("%d%s", v[i], (i % 5 == 4) ? ("\\n"): (" "));
- }
- */
- return 0;
- }
- /*
- * 函数:SeletSort
- * 用法:SeletSort(v);
- * -------------------
- * 函数用选择排序算法对整型数组进行排序。
- */
- void SeletSort(int v[], int n)
- {
- int lh, rh, temp;
- for (lh = 0; lh < n; lh++) {
- rh = lh;
- for (int i = lh + 1; i < n; i++) {
- if (v[i] < v[rh]) {
- rh = i;
- }
- }
- temp = v[rh];
- v[rh] = v[lh];
- v[lh] = temp;
- }
- }
- /*
- * 函数:SortIntArray
- * 用法:SortIntArray(v, n);
- * ------------------------
- * 函数使用合并排序算法对整型数组进行排序。
- */
- void SortIntArray(int v[], int n)
- {
- int n1, n2;
- int *arr1, *arr2;
- if (n <= 1) return;
- n1 = n / 2;
- n2 = n - n1;
- arr1 = CopySubArray(v, 0, n1);
- arr2 = CopySubArray(v, n1, n);
- SortIntArray(arr1, n1);
- SortIntArray(arr2, n2);
- Merge(v, arr1, n1, arr2, n2);
- free(arr1);
- free(arr2);
- }
- /*
- * 函数:Merge
- * 用法:Merge(v, arr1, n1, arr2, n2);
- * ----------------------------------
- * 函数把两个已经排序好的数组合并成一个排序的数组。
- */
- void Merge(int v[], int arr1[], int n1, int arr2[], int n2)
- {
- int p, p1, p2;
- p = p1 = p2 = 0;
- while (p1 < n1 && p2 < n2) {
- if (arr1[p1] < arr2[p2]) {
- v[p++] = arr1[p1++];
- }
- else {
- v[p++] = arr2[p2++];
- }
- }
- while (p1 < n1) {
- v[p++] = arr1[p1++];
- }
- while (p2 < n2) {
- v[p++] = arr2[p2++];
- }
- }
- /*
- * 函数:CopySubArray
- * 用法:CopySubArray(v, 0, n);
- * ---------------------------
- * 函数把原数组从start到n的元素复制到一个新的数组。
- */
- int *CopySubArray(int v[], int start, int n)
- {
- int *result;
- result = (int *)malloc(sizeof(int) * n);
- for (int i = 0; i < n; i++) {
- result[i] = v[start + i];
- }
- return result;
- }
- /*
- * 函数:quicksort
- * 用法:quicksort(v, N);
- * ---------------------
- * 函数对数组进行排序,使用的是快速排序算法。
- */
- void quicksort(int v[], int n)
- {
- int boundary;
- if (n < 2) return;
- boundary = partition(v, n);
- quicksort(v, boundary);
- quicksort(v + boundary + 1, n - boundary - 1);
- }
- /*
- * 函数:partition
- * 用法:boundary = partition(v, n);
- * --------------------------------
- * 函数对数组进行分割,以便使用快速排序算法。
- */
- int partition(int v[], int n)
- {
- int lh, rh, pivot, temp;
- pivot = v[0];
- lh = 1;
- rh = n - 1;
- while (1) {
- while (lh < rh && v[rh] >= pivot) {
- rh--;
- }
- while (lh < rh && v[lh] < pivot) {
- lh++;
- }
- if (lh == rh) break;
- temp = v[lh];
- v[lh] = v[rh];
- v[rh] = temp;
- }
- if (v[lh] >= pivot) return 0;
- v[0] = v[lh];
- v[lh] = pivot;
- return lh;
- }
- /*
- * 函数:InsertSort
- * 用法:InsertSort(v, N);
- * ----------------------
- * 函数用插入排序算法对整型数组进行排序。
- */
- void InsertSort(int v[], int n)
- {
- int temp;
- for (int i = 0; i < n; i++) {
- for (int j = i + 1; j > 0; j--) {
- if (v[j] < v[j - 1]) {
- temp = v[j];
- v[j] = v[j - 1];
- v[j - 1] = temp;
- }
- }
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/1206201512849.html
来源: http://www.codesnippet.cn/detail/1206201512849.html