锘??xml version="1.0" encoding="utf-8" standalone="yes"?>国产精品激情偷乱一区二区∴,国产一区二区三区观看,亚洲春色另类小说http://www.shnenglu.com/bon/zh-cnSat, 29 Nov 2025 04:11:34 GMTSat, 29 Nov 2025 04:11:34 GMT60merge sort pitfallshttp://www.shnenglu.com/bon/archive/2009/04/30/81561.htmlbonbonThu, 30 Apr 2009 05:57:00 GMThttp://www.shnenglu.com/bon/archive/2009/04/30/81561.htmlhttp://www.shnenglu.com/bon/comments/81561.htmlhttp://www.shnenglu.com/bon/archive/2009/04/30/81561.html#Feedback0http://www.shnenglu.com/bon/comments/commentRss/81561.htmlhttp://www.shnenglu.com/bon/services/trackbacks/81561.html Now I would like to scan all basic algorithms, especially sorting and searching.
Let me first present a classic sorting algorithm - merge sort. Here is my code. Before I reach here, some mistakes are made, thus I note these "pitfalls" in the code
#include <stdlib.h> #include <stdio.h> #define MAX 1e9 // the biggest possible value of a int number is 2^31 - 1 which is approximately 10^9 #define SIZE 10
int *a; int *b; int *c;
// merge [p, q] and [q+1, r], where within each range number are sorted void merge(int p, int q, int r) { int k; int length = r - p +1; // the length the range to be merge for (k = 0; k < q - p + 1; k++) { b[k] = a[p + k]; // copy number in a[p, q] to b } b[k] = MAX; // b[k] = MAX, not b[k+1]=MAX for (k = 0; k < r - q; k++) { c[k] = a[q + 1 + k]; // copy number in a[q+1, r] to c } c[k] = MAX; // c[k] = MAX, not c[k+1]=MAX
/* BEGIN merging */ int i = 0; int j = 0; for (k=0;k<length;k++) { // do exactly length times of copy if (b[i] < c[j]) { a[p + k] = b[i++]; // be careful! a[p, r] is a whole range now, and watch out the base "p" } else { a[p + k] = c[j++]; } } }
void merge_sort(int l, int u) { if (l == u) return; // when to stop recursion? only one number needs no sorting int m = (l + u)/2; merge_sort(l, m); merge_sort(m + 1, u); merge(l, m, u); }
int main() { a = (int*)malloc(SIZE * sizeof(int)); b = (int*)malloc(SIZE * sizeof(int)); // cache, avoid many "malloc" in the merge function c = (int*)malloc(SIZE * sizeof(int)); // this trick is from "Programming Pearls" int i; for (i = 0; i < SIZE; i++) { a[i] = SIZE - i; } merge_sort(0, SIZE - 1); // watch out the range for (i = 0; i < SIZE; i++) { printf("%d\n", a[i]); } return 1; }