mySort.h
#ifndef MYSORT_H_INCLUDED #define MYSORT_H_INCLUDED /* 交换排序:冒泡排序,快速排序 */ void bubbleSort(int arr[], int arrLen); int slipForQuickSort(int arr[], int arrLeft, int arrRight); void quickSort(int arr[], int arrLeft, int arrRight); /* 选择排序:直接选择排序,堆排序 */ void directSelectSort(int arr[], int arrLen); void heapAdjust(int arr[], int parent, int arrLen); void heapSort(int arr[], int arrLen); /* 插入排序:直接插入排序,希尔排序 */ void directInsertSort(int arr[], int arrLen); void shellSort(int arr[], int arrLen); /* 合并排序:归并排序 */ void mergeSort(int arr[], int temparr[], int left, int right); void merge(int array[], int temparray[], int left, int middle, int right); #endif // MYSORT_H_INCLUDED
mySort.c
#include "mysort.h" #include "stdio.h" void playArr(int arr[], int len) { int i = 0; for (i = 0; i < len - 1; i++) { printf("%d\t", arr[i]); } printf("\n"); return; } void swapNum(int *a, int *b) { int tmp; tmp = *a; *a = *b; *b = tmp; return; } /* 冒泡排序是交换排序,O(N^2) */ void bubbleSort(int arr[], int arrLen) { int i; int j; for (i = 0; i < arrLen; i++) { for (j = arrLen - 1; j > i; j--) { if (arr[j] < arr[i]) { swapNum(&arr[i], &arr[j]); } } } return; } /* 快速排序是交换排序,O(N^2),平均复杂度:N(logN) int arrLeft, int arrRight 是数组下标 */ void quickSort(int arr[], int arrLeft, int arrRight) { int i; if (arrLeft < arrRight) { i = slipForQuickSort(arr, arrLeft, arrRight); quickSort(arr, arrLeft, i - 1); quickSort(arr, i + 1, arrRight); } return; } int slipForQuickSort(int arr[], int arrLeft, int arrRight) { int baseNum = arr[arrLeft]; while (arrLeft < arrRight) { //从右到左查询比baseNum小的数字 while ((arrLeft < arrRight) && (arr[arrRight] >= baseNum)) { arrRight--; } arr[arrLeft] = arr[arrRight]; //在右边找到之后将比baseNum小的数字移动到数组的左边 //从左到右查询比baseNum大的数字 while ((arrLeft < arrRight) && (arr[arrLeft] <= baseNum)) { arrLeft++; } arr[arrRight] = arr[arrLeft]; //在左边找到之后将比baseNum大的数字移动到数组的右边 } arr[arrLeft] = baseNum; //把基准数字放到arrLeft位置上,此时arrLeft左边都是比baseNum小的数字,右边都是比它大的数字 return arrLeft; } /* 直接插入排序:O(n^2) */ void directSelectSort(int arr[], int arrLen) { int i; int j; int baseNum; for (i = 0; i < arrLen; i++) { baseNum = i; //在i的右侧找到最下的一个数字,记录下标 for (j = i + 1; j < arrLen; j++) { if (arr[j] < arr[baseNum]) { baseNum = j; } } //将最小的数字移动到当前位置 swapNum(&arr[i], &arr[baseNum]); } return; } /* 堆排序:O(NlogN) */ void heapSort(int arr[], int arrLen) { int i; //二叉树父节点的下标为i时,左右孩子接到为2i+1,2i+2。 for (i = arrLen / 2 - 1; i >= 0; i--) { heapAdjust(arr, i, arrLen); } for (i = arrLen - 1; i >= 0 /*arrLen - top */; i--) { swapNum(&arr[0], &arr[i]); //将大数放到数组最右边 heapAdjust(arr, 0, i - 1); //将剩余的数字从新构建大根堆 } return; } void heapAdjust(int arr[], int parent, int arrLen) { int tmp; int leftChild; tmp = arr[parent]; //取出父节点的值并保持 leftChild = 2 * parent + 1; //找到父节点的左孩子 while (leftChild < arrLen) { if ((leftChild + 1 < arrLen) && (arr[leftChild] < arr[leftChild +1])) { leftChild++; } if (tmp >= arr[leftChild]) { break; } arr[parent] = arr[leftChild]; parent = leftChild; leftChild = 2 * parent + 1; } arr[parent] = tmp; return; } /* 直接插入排序:O(N^2) 将N-M个无序数字,插入前面M个有序数字中 */ void directInsertSort(int arr[], int arrLen) { int i; int j; int tmp; for (i = 1; i < arrLen; i++) { tmp = arr[i]; for (j = i - 1; ((j >= 0) && (arr[j] > tmp)); j--) { arr[j + 1] = arr[j]; } arr[j + 1] = tmp; } } /* 希尔排序:平均为:O(N^3/2) 最坏: O(N^2) */ void shellSort(int arr[], int arrLen) { int i; int j; int tmp; int addNum; addNum = arrLen / 2; //增量 while (addNum >= 1) { for (i = addNum; i < arrLen; i++) { tmp = arr[i]; for (j = i - addNum; ((j >= 0) && (tmp < arr[j])); j = j - addNum) { arr[j + addNum] = arr[j]; } arr[j + addNum] = tmp; } addNum /= 2; } return; } /* 归并排序: 时间:O(NlogN) 空间:O(N) int left, int right 为数组下标 */ void mergeSort(int arr[], int temparr[], int left, int right) { int middle; if (left < right) { middle = (left + right) / 2; //拆分位置 mergeSort(arr, temparr, left, middle); mergeSort(arr, temparr, middle + 1, right); merge(arr, temparr, left, middle + 1, right); } return; } void merge(int array[], int temparray[], int left, int middle, int right) { int i; //左指针尾 int leftEnd = middle - 1; //右指针头 int rightStart = middle; //临时数组的下标 int tempIndex = left; //数组合并后的length长度 int tempLength = right - left + 1; //先循环两个区间段都没有结束的情况 while ((left <= leftEnd) && (rightStart <= right)) { //如果发现有序列大,则将此数放入临时数组 if (array[left] < array[rightStart]) temparray[tempIndex++] = array[left++]; else temparray[tempIndex++] = array[rightStart++]; } //判断左序列是否结束 while (left <= leftEnd) temparray[tempIndex++] = array[left++]; //判断右序列是否结束 while (rightStart <= right) temparray[tempIndex++] = array[rightStart++]; //交换数据 for (i = 0; i < tempLength; i++) { array[right] = temparray[right]; right--; } return; }
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。