一：快速排序

#include <stdio.h> #include <stdlib.h> #include <time.h> #include <sys/timeb.h>#define MAX 10//獲取時間，毫秒 long getTime() {struct timeb tb;ftime(&tb);return tb.time * 1000 + tb.millitm; }//打印 void PrintArr(int* arr, int len) {for (int i = 0; i < len; i++){printf("%d ", arr[i]);} }//快速排序 void Quick_Sort(int arr[],int start,int end) {int i = start;int j = end;int temp = arr[start];//temp是基數，默認從0位開始if (j>i){//第一次循環while (j>i){//如原始數據：4 2 8 0//第一個基數為4，變為： ' ' 2 8 0 i指向空格，j指向0if ((arr[j]>=temp))//注意i和j其中一個或者共同 必須有等于情況{//如若j指向的0是9,比4大，j往前走j--;}//J指向的比4小，交換位置 i 填空//0 2 8 ' ';arr[i] = arr[j];//i指向的數如若比4小，如0，則i++if ((arr[j] <= temp)){//如若j指向的0是9,比4大，j往前走i++;}//i指向的數如若比4大，如8，則填空//0 2 ' ' 8arr[j] = arr[i];}//第一輪循環結束后， i和j同時指向空格' ' 把temp填上//0 2 4 8arr[i] = temp;//分治開始，左右各開始 回調Quick_Sort(arr, start, i - 1);//左邊 i指向0 j指向2Quick_Sort(arr, i + 1, end);} }int main(void) {srand((unsigned int)time(NULL));int arr[MAX];for (int i = 0; i < MAX;i++){arr[i] = rand() % MAX;}int len = sizeof(arr) / sizeof(arr[0]);printf("快速排序前：");PrintArr(arr, MAX);//printf("%d\n", len);long t_start = getTime();Quick_Sort(arr,0,len-1);long t_end = getTime();printf("\n");printf("快速排序后：");PrintArr(arr, MAX);printf("\n");printf("快速排序共花費%ld毫秒\n", t_end - t_start);return 0; }

二：堆排序

#include <stdio.h> #include <stdlib.h> #include <time.h>#define MAX 10 /** 數組就相當于滿二叉樹*///打印 void PrintArr(int* arr, int len) {for (int i = 0; i < len; i++){printf("%d ", arr[i]);}printf("\n"); }//交換 void MySwap(int *arr,int index,int max) {int temp = arr[index];arr[index] = arr[max];arr[max] = temp; }//開始調整 index為調整的開始位置 初始化時為0 下標為3 void HeapJust(int *arr,int index,int len) {int max = index;int lChild = index * 2 + 1;//3int rChild = index * 2 + 2;//9if (lChild<len && (arr[lChild]>arr[max])){//lChild<len 如果0沒有左右子樹，len=6 上面lChild=7 為空則不執行max = lChild;//3>0}if (rChild<len && (arr[rChild]>arr[max])){//lChild<len 如果0沒有左右子樹，len=6 上面lChild=7 為空則不執行max = rChild;//9>3}//考慮樹根8 左右7 1 index=max就不用交換if (index!=max){MySwap(arr, index, max);//交換以后，需要考慮后面的也要交換HeapJust(arr, max, len);} }void HeapSort(int *arr,int len) {//1.初始化 將最大數調到頂端 從下往上調//默認起始位置為倒數第二排 下標為3的位置for (int i = len / 2 - 1; i >= 0;i--)//i--后到下標為2的位置 也就是8{//開始調整HeapJust(arr, i,len);}//2.將頂端依次和底部調整位置，從頭開始調整排序for (int i = len - 1; i >= 0;i--){MySwap(arr, 0, i);//開始為0和9交換//從頭開始調整HeapJust(arr, 0, i);//樹頂和樹尾交換了幾次，最大幾個數就已經放在尾部了，len為i} } int main(void) {//int arr[] = { 4, 2, 8, 0, 5, 7, 1, 3, 9 };srand((unsigned int)time(NULL));int arr[MAX];for (int i = 0; i < MAX; i++){arr[i] = rand() % MAX;}int len = sizeof(arr) / sizeof(arr[0]);PrintArr(arr, len);//printf("%d", len);HeapSort(arr, len);PrintArr(arr, len);return 0; }

總結

以上是生活随笔為你收集整理的数据结构二：排序（快速排序和堆排序）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。