常用排序算法

2019-11-06 08:56:08

字体：大中小

来源：转载

供稿：网友

常用的几种排序算法及测试

#include <stdio.h>#include <stdlib.h>#include <unistd.h>#include <time.h>#define ARR_LEN 1000000/* *************** * 冒泡升序排序 * **************/void maopaoSort(int arr[], int len){ int i, j, temp; if (NULL == arr) return; for (i=0; i<len; i++) { for (j=1; j<len-i; j++) { if (arr[j-1] > arr[j]) { temp = arr[j-1]; arr[j-1] = arr[j]; arr[j] = temp; } } }}/****************** * 快速排序升序 * ****************/void quickSort(int arr[], int len){ int low, high; int compValue; low = 0; high = len-1; if (high <= 0) return; compValue = arr[low]; while (low < high) { while (compValue < arr[high] && high > low) { high--; } if (high > low) { arr[low++] = arr[high]; } while (compValue > arr[low] && high > low) { low++; } if (high > low) { arr[high--] = arr[low]; } } arr[low] = compValue; quickSort(arr, low); quickSort(&arr[low+1], len-low-1);}/* ******************* * 希尔排序升序 * arr: 排序的数组 * len: 数组的长度 * *******************/void shellSort(int arr[], int len){ int i, j, k; int temp; int gap = len; do { gap = gap / 3 + 1; for (i=gap; i<len; i+=gap) { k = i; temp = arr[k]; for (j=i-gap; (j>=0) && (arr[j]>temp); j-=gap) { arr[j+gap] = arr[j]; k = j; } arr[k] = temp; } } while (gap > 1);}/* *************** * 选择排序升序 * **************/void selectSort(int arr[], int len){ int i, j, temp; int curIndex; if (NULL == arr) return; for (i=0; i<len; i++) { curIndex = i; for (j=i+1; j<len; j++) { if (arr[curIndex] > arr[j]) { curIndex = j; } } if (curIndex != i) { temp = arr[i]; arr[i] = arr[curIndex]; arr[curIndex] = temp; } }}/************** *创建随机数组 *************/void createRandomArr(int arr[], int len){ int i; if (arr == NULL) return ; srandom((unsigned int)time(NULL)); for (i=0; i<len; i++) { arr[i] = random() % ARR_LEN + 1; }}/*************** * 打印数组 * ************/void PRintArr(int arr[], int len){ int i; if (arr == NULL) return ; for (i=0; i<len; i++) printf("%d ", arr[i]); printf("/n");}int main(void){ int arr[ARR_LEN]; time_t start_time, end_time; createRandomArr(arr, ARR_LEN); //printArr(arr, ARR_LEN); printf("冒泡排序开始~/n"); start_time = time(NULL); maopaoSort(arr, ARR_LEN); end_time = time(NULL); printf("冒泡排序结束, 耗时: %ld/n", end_time - start_time); createRandomArr(arr, ARR_LEN); printf("选择排序开始~/n"); start_time = time(NULL); selectSort(arr, ARR_LEN); end_time = time(NULL); printf("选择排序结束, 耗时: %ld/n", end_time - start_time); createRandomArr(arr, ARR_LEN); printf("希尔排序开始~/n"); start_time = time(NULL); shellSort(arr, ARR_LEN); end_time = time(NULL); printf("希尔排序结束, 耗时: %ld/n", end_time - start_time); createRandomArr(arr, ARR_LEN); printf("快速排序开始~/n"); start_time = time(NULL); quickSort(arr, ARR_LEN); end_time = time(NULL); printf("快速排序结束, 耗时: %ld/n", end_time - start_time); //printArr(arr, ARR_LEN); return 0;}

上一篇：当美女遇上足球，请吾好你的小心脏！

下一篇：安装visual studio