几种常用排序的实现，插入、冒泡、快速、归并、堆排序
稳定的有：插入、冒泡、归并、基数排序
不稳定的有：快速排序、堆排序
尽管用C实现，但是写得很有java风格
/* * 插入排序 */ void myinsertSort(int a[], int len) { int tmp; int i; for (i = 1; i < len; i ++) { while (a[i] < a[i - 1] && i >=1 ) { tmp = a[i - 1]; a[i - 1] = a[i]; a[i] = tmp; i --; } } } /** * 冒泡排序 */ void mybubbleSort(int a[], int len) { int tmp; int i,j; for (i = 0; i < len; i ++) for ( j = i + 1; j < len ; j ++) if (a[j - 1] > a [j]) { tmp = a[i]; a[i] = a[j]; a[j] = tmp; } } /* * 快速排序 */ void myquickSort(int a[], int begin, int end) { if (begin < end) { int index; index = partition(a, begin, end); myquickSort(a, begin, index - 1); myquickSort(a, index + 1, end); } } /* * 划分函数 */ int partition(int a[], int begin, int end) { int key = a[end]; int i,j = begin - 1; int tmp; for (i = begin; i < end ; i ++) { if (a[i] < key) { j ++; tmp = a[i]; a[i] = a[j]; a[j] = tmp; } } j ++; tmp = a[j]; a[j] = a[end]; a[end] = tmp; printf("%d/n", j); print(a, end - begin + 1); return j; } /** * 归并排序 */ /** * merge函数,iuputArray[beginIndex……midIndex]和iuputArray[midIndex……endIndex] * 是有序的，将他们合并成有序的序列iuputArray[beginIndex……endIndex]即可 */ void merge (int inputArray[], int beginIndex, int midIndex, int endIndex) { int result[endIndex - beginIndex + 1]; int i = beginIndex; int j = midIndex + 1; int k = 0; while (i <= midIndex && j <= endIndex) { if (inputArray [i] <= inputArray [j]) { result[k ++] = inputArray [i ++]; } else { result[k ++] = inputArray [j ++]; } } while (j <= endIndex) result [k ++] = inputArray [j ++]; while (i <= midIndex) result [k ++] = inputArray [i ++]; // for (k = 0; k < endIndex - beginIndex + 1; k ++) // printf("%d ",result[k]); // printf("/n"); //最后一步要赋值，不然result[]是局部变量，当前函数执行完毕，就会销毁变量。 for (k = 0; k < endIndex - beginIndex + 1;k ++) inputArray[beginIndex + k] = result[k]; } /* * 归并排序中调用merge函数 */ void mymergeSort(int a[], int begin, int end) { // static count; if (begin < end) { int mid = (begin + end)/2; mymergeSort (a, begin, mid); mymergeSort (a, mid + 1, end); merge (a, begin, mid, end); } // printf("the number of reverse-order pair is %d", count); } /** * 堆排序 */ /*************************************************************************/ /** * 堆调整 */ void heapAdjust(int array[], int beginIndex, int endIndex, int index) { int length = endIndex - beginIndex + 1; int largestIndex = index; int leftIndex = 2 * index + 1; //下标从0开始，可以自己做实验 int rightIndex = 2 * index + 2; if (leftIndex <= length - 1 && array[leftIndex] > array[largestIndex] ) { largestIndex = leftIndex; } if (rightIndex <= length - 1 && array[rightIndex] > array[largestIndex] ) { largestIndex = rightIndex; } if (largestIndex != index) { int temp = array [largestIndex]; array [largestIndex] = array [index]; array [index] = temp; heapAdjust (array, beginIndex, endIndex, largestIndex); } } /** * 建堆 */ void heapBuild (int array[], int len ) { int i = 0; for (i = len/2 -1; i >= 0; i --) { heapAdjust (array, 0, len - 1, i); } } void myheapSort(int array[], int len) { int result[len]; heapBuild (array,len); int i, k =0; for (i = len - 1 ; i >= 0; i --) { result [k ++] = array [0]; int temp = array [0]; array [0] = array [i]; array [i] = temp; heapAdjust (array, 0, i - 1, 0); } for (k = 0; k < len ; k ++) printf("%d ", result[k]); }
