一、插入类排序：
1.直接插入排序
#includevoid print(int a[], int n) { for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("n"); } void insertSort(int a[], int n) { int i, j; for ( i = 1; i < n; i++) { int key = a[i]; //注意有等号则算法就不稳定了 for ( j = i - 1; j >= 0 && a[j] > key; j--) { a[j + 1] = a[j]; } a[j + 1] = key; } } int main() { printf("插入排序：n"); int a[] = { 2,4,6,8,10,1,3,5,7,9 }; print(a, sizeof(a) / sizeof(a[0])); insertSort(a, 10); print(a, sizeof(a) / sizeof(a[0])); return 0; }
2.希尔排序
//方式一 #includevoid print(int a[], int n) { for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("n"); } void shellSort(int a[], int n) { int gap = 3; int i, j; while (gap--) { for ( i = gap; i < n; i++) { int key = a[i]; for ( j = i - gap; j >= 0 && a[j] > key; j-=gap) { a[j + gap] = a[j]; } a[j + gap] = key; } } } int main() { int a[] = { 2,4,6,8,10,1,3,5,7,9 }; printf("希尔排序：n"); print(a, sizeof(a) / sizeof(a[0])); shellSort(a, 10); print(a, sizeof(a) / sizeof(a[0])); return 0; } //方式二（注意gap差别） #include void print(int a[], int n) { for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("n"); } void shellSort(int a[], int n) { int gap = n; while (gap>1) { gap = gap / 3 + 1; int i, j; //int i, j; //这里i++而不是i+gap原因是比较下一组（隔相同步数的为一组） for ( i = gap; i < n; i++) { int key = a[i]; for (j = i - gap; j >= 0 && key < a[j]; j-=gap) { a[j + gap] = a[j]; } a[j + gap] = key; } //gap--; } } int main() { int a[] = { 1,3,5,7,9,2,4,6,8,10 }; printf("希尔排序：n"); print(a, sizeof(a) / sizeof(a[0])); shellSort(a, sizeof(a) / sizeof(a[0])); print(a, sizeof(a) / sizeof(a[0])); return 0; }
二、选择类排序
1.简单选择排序
//方式一--先排最大的，即将最大的排在后面 #includevoid print(int a[], int n) { for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("n"); } void selectSort(int a[], int n) { int i, j; for ( i = 0; i < n - 1; i++) { //max为当前最大值下标，从下标为0到下标为max-1中找最大的，不断更新max int max = n-1-i; for (j = 0; j < n - 1 - i; j++) { if (a[j] > a[max]) { max = j; } } if (max != j) { int temp = a[j]; a[j] = a[max]; a[max] = temp; } } } //或用以下写法 int main() { int a[] = { 1,3,5,7,9,2,4,6,8,10 }; printf("选择排序：n"); print(a, sizeof(a) / sizeof(a[0])); selectSort(a, sizeof(a) / sizeof(a[0])); print(a, sizeof(a) / sizeof(a[0])); return 0; } //方式二--先排最小的，即将最小的放在前面 #include void print(int a[], int n) { for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("n"); } void selectSort(int a[], int n) { for (int i = 0; i < n - 1; i++) { int min = i; for (int j = i + 1; j < n; j++) { if (a[j] < a[min]) { int temp = a[j]; a[j] = a[min]; a[min] = temp; } } } } int main() { int a[] = { 1,3,5,7,9,2,4,6,8,10 }; printf("选择排序：n"); print(a, sizeof(a) / sizeof(a[0])); selectSort(a, sizeof(a) / sizeof(a[0])); print(a, sizeof(a) / sizeof(a[0])); return 0; } //方式三--在一趟中同时找最大和最小元素，将最大元素和最小元素进行交换 #include #include void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } void PrintArray(int array[], int size) { for (int i = 0; i < size; ++i) { printf("%d ", array[i]); } printf("n"); } void SelectSort(int* a, int n) { assert(a); int begin = 0, end = n - 1; while (begin < end) { int min = begin, max = begin; for (int i = begin; i <= end; i++) { if (a[i] >= a[max]) max = i; if (a[i] < a[min]) min = i; } //最小的放在 swap(&a[begin], &a[min]); //如果最大的位置在begin位置 //说明min是和最大的交换位置 //这个时候max的位置就发生了变换 //max变到了min的位置 //所以要更新max的位置 if (begin == max) max = min; swap(&a[end], &a[max]); ++begin; --end; //PrintArray(a, n); } } int main() { int a[] = { 3, 4, 6, 1, 2, 8, 0, 5, 7 }; SelectSort(a, sizeof(a) / sizeof(int)); PrintArray(a, sizeof(a) / sizeof(int)); return 0; }
2.堆排序
#includevoid print(int a[], int n) { for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("n"); } //n表示父节点，size表示总节点个数 void adjustDown(int a[], int size, int n) { //n相当于parent int child = n * 2 + 1; while (child < size) { //若要排降序，只要该为a[child+1] a[child]) { child = child + 1; } if (a[child] > a[n]) { int temp = a[child]; a[child] = a[n]; a[n] = temp; n = child; child = child * 2 + 1; } else { return; } } } void heapSort(int a[], int n) { //建堆 for (int i = (n - 2) / 2; i >= 0; i--) { adjustDown(a, n, i); } //利用堆删除思想排序 int end = n - 1; while (end) { int temp = a[0]; a[0] = a[end]; a[end] = temp; //heapSort(a, end); //上一次end的下标刚好是下一次要排的元素个数 adjustDown(a, end, 0); end--; } } int main() { int a[] = { 1,3,5,7,9,2,4,6,8,10 }; printf("堆排序：n"); print(a, sizeof(a) / sizeof(a[0])); heapSort(a, sizeof(a) / sizeof(a[0])); print(a, sizeof(a) / sizeof(a[0])); return 0; }
三、交换类排序
1.冒泡排序
#includevoid print(int a[], int n) { for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("n"); } void bubbleSort(int a[], int n) { for (int i = 0; i < n - 1; i++) { int flag = 1; for (int j = 0; j < n - 1 - i; j++) { if (a[j + 1] < a[j]) { int temp = a[j + 1]; a[j + 1] = a[j]; a[j] = temp; flag = 0; } } if (flag == 1) { break; } } } int main() { int a[] = { 2,4,6,8,10,1,3,5,7,9 }; printf("冒泡排序：n"); print(a, sizeof(a) / sizeof(a[0])); bubbleSort(a, sizeof(a) / sizeof(a[0])); print(a, sizeof(a) / sizeof(a[0])); return 0; }
2.快速排序
//有三种方式取基准值，分别是PartSort1、PartSort2、PartSort3 #include#include #include #include typedef int DataType; // 动态 typedef struct Stack { DataType* array; int capacity; int top; // 标记栈顶---实际就是顺序表中的有效元素的个数 }Stack; void StackInit(Stack* ps,int n) { assert(ps); ps->array = (DataType*)malloc(sizeof(DataType) * n); if (NULL == ps->array) assert(0); ps->capacity = n; ps->top = 0; } void StackCheckCapacity(Stack* ps) { assert(ps); if (ps->top == ps->capacity) { int newCapacity = (ps->capacity << 1); // 1. 开辟新空间 DataType* temp = (DataType*)malloc(sizeof(DataType) * newCapacity); if (NULL == temp) assert(0); // 2. 拷贝元素 memcpy(temp, ps->array, sizeof(DataType) * ps->capacity); // 3. 释放旧空间,使用新空间 free(ps->array); ps->array = temp; ps->capacity = newCapacity; } } // 入栈---尾插 void StackPush(Stack* ps, DataType data) { StackCheckCapacity(ps); ps->array[ps->top] = data; ps->top++; } // 检测栈是否为空，如果为空返回真，否则返回假 int StackEmpty(Stack* ps) { assert(ps); return 0 == ps->top; } // 出栈 void StackPop(Stack* ps) { if (StackEmpty(ps)) return; ps->top--; } // 获取栈顶元素 DataType StackTop(Stack* ps) { assert(ps); // return ps->array[--ps->top]; // 错误写法 return ps->array[ps->top - 1]; // 正确的 } void PrintArray(int array[], int size) { for (int i = 0; i < size; ++i) { printf("%d ", array[i]); } printf("n"); } void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } // 三数取中法，三个中取一个中间值 int GetMidIndex(int* a, int begin, int end) { int mid = begin + ((end - begin) >> 1); if (a[begin] < a[mid]) { if (a[mid] < a[end]) { return mid; } else if (a[begin] > a[end]) { return begin; } else { return end; } } else // begin >= mid { if (a[mid] > a[end]) { return mid; } else if (a[begin] < a[end]) { return begin; } else { return end; } } } int PartSort1(int* a, int begin, int end) { int midindex = GetMidIndex(a, begin, end); swap(&a[begin], &a[midindex]); int key = a[begin]; int start = begin; while (begin < end) { // end 找小 while (begin < end && a[end] >= key) --end; // begin找大 while (begin < end && a[begin] <= key) ++begin; swap(&a[begin], &a[end]); } //最后的交换一定要保证a[begin] < a[start], 所以要从右边走 swap(&a[begin], &a[start]); return begin; } int PartSort2(int* a, int begin, int end) { //begin是坑 int key = a[begin]; while (begin < end) { while (begin < end && a[end] >= key) --end; // end给begin这个坑，end就变成了新的坑。 a[begin] = a[end]; while (begin < end && a[begin] <= key) ++begin; // end给begin这个坑，begin就变成了新的坑。 a[end] = a[begin]; } a[begin] = key; return begin; } int PartSort3(int* a, int begin, int end) { int midindex = GetMidIndex(a, begin, end); swap(&a[begin], &a[midindex]); int key = a[begin]; int prev = begin; int cur = begin + 1; while (cur <= end) { // cur找小，把小的往前翻，大的往后翻 if (a[cur] < key && ++prev != cur) swap(&a[cur], &a[prev]); ++cur; } swap(&a[begin], &a[prev]); return prev; } void insertSort(int a[], int n) { int j; for (int i = 1; i < n; i++) { int temp = a[i]; for (j = i - 1; a[j] > temp && j >= 0; j--) { a[j + 1] = a[j]; } a[j + 1] = temp; } } void QuickSort(int* a, int left, int right) { if (left >= right) return; if (right - left + 1 < 10) { insertSort(a + left, right - left + 1); } else { int div = PartSort1(a, left, right); //[left, div-1] //[div+1, right] QuickSort(a, left, div - 1); QuickSort(a, div + 1, right); } } //用栈模拟递归，用队列也可以实现 void QuickSortNor(int array[], int size) { Stack s; StackInit(&s,10); int left = 0; int right = size; StackPush(&s, right); StackPush(&s, left); while (!StackEmpty(&s)) { left = StackTop(&s); StackPop(&s); right = StackTop(&s); StackPop(&s); if (right - left <= 16) insertSort(array + left, right - left); else { int div = PartSort2(array, left, right); // 基准值的左侧：[left, div) // 基准值的右侧：[div+1, right); StackPush(&s, right); StackPush(&s, div + 1); StackPush(&s, div); StackPush(&s, left); } } } int main() { int a[] = { 3, 4, 6, 1, 2, 8, 0, 5, 7 }; printf("快速排序：n"); PrintArray(a, sizeof(a) / sizeof(int)); //QuickSort(a, 0, sizeof(a) / sizeof(int) - 1); QuickSortNor(a, sizeof(a) / sizeof(int) ); PrintArray(a, sizeof(a) / sizeof(int)); return 0; }
四、归并排序：
//有递归和非递归两种方式，已测试 #include#include #include #include void PrintArray(int array[], int size) { for (int i = 0; i < size; ++i) { printf("%d ", array[i]); } printf("n"); } void _MergeSort(int* a, int left, int right, int* tmp) { if (left >= right) return; int mid = left + ((right - left) >> 1); // [left, mid] // [mid+1, right] _MergeSort(a, left, mid, tmp); _MergeSort(a, mid + 1, right, tmp); int begin1 = left, end1 = mid; int begin2 = mid + 1, end2 = right; int index = left; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] <= a[begin2]) tmp[index++] = a[begin1++]; else tmp[index++] = a[begin2++]; } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1)); } //封装一下，让用户好调用 void MergeSort(int* a, int n) { assert(a); int* tmp = (int*)malloc(sizeof(int) * n); _MergeSort(a, 0, n - 1, tmp); free(tmp); } void merge(int* a, int left, int mid, int right, int* tmp) { // [left, mid] // [mid+1, right] int begin1 = left, end1 = mid; int begin2 = mid + 1, end2 = right; int index = left; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] <= a[begin2]) tmp[index++] = a[begin1++]; else tmp[index++] = a[begin2++]; } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1)); } void mergePass(int* arr, int k, int n, int* temp) { int i = 0; //从前往后,将2个长度为k的子序列合并为1个 while (i < n - 2 * k + 1) { merge(arr, i, i + k - 1, i + 2 * k - 1, temp); i += 2 * k; } //合并区间[i, n - 1]有序的左半部分[i, i + k - 1]以及不及一个步长的右半部分[i + k, n - 1] if (i < n - k) { merge(arr, i, i + k - 1, n - 1, temp); } } // 归并排序非递归版 void MergeSortNonR(int* arr, int length) { int k = 1; int* temp = (int*)malloc(sizeof(int) * length); while (k < length) { mergePass(arr, k, length, temp); k *= 2; } free(temp); } int main() { int a[10] = { 4,1,3,2,7,6,5,9,10,8 }; printf("归并排序：n"); PrintArray(a, 10); MergeSort(a, 10); PrintArray(a, 10); //printf("归并排序--非递归：n"); //MergeSortNonR(a, 10); //PrintArray(a, 10); return 0; }
五、计数排序：
#include#include #include #include void PrintArray(int array[], int size) { for (int i = 0; i < size; ++i) { printf("%d ", array[i]); } printf("n"); } void CountSort(int* a, int n) { int max = a[0], min = a[0]; for (int i = 0; i < n; ++i) { if (a[i] > max) max = a[i]; if (a[i] < min) min = a[i]; } //找到数据的范围 int range = max - min + 1; int* countArray = (int*)malloc(range * sizeof(int)); memset(countArray, 0, sizeof(int) * range); //存放在相对位置，可以节省空间 for (int i = 0; i < n; ++i) { countArray[a[i] - min]++; } //可能存在重复的数据，有几个存几个 int index = 0; for (int i = 0; i < range; ++i) { while (countArray[i]--) { a[index++] = i + min; } } } //该方式好理解 void CountSort2(int array[], int size) { // 0. 获取数据的范围 int minValue = array[0]; int maxValue = array[0]; for (int i = 1; i < size; ++i) { if (array[i] > maxValue) maxValue = array[i]; if (array[i] < minValue) minValue = array[i]; } // 数据范围在[minValue, maxValue] 假设数据在1000-1009，其实只需要10个空间就可以 int range = maxValue - minValue + 1; int* count = (int*)calloc(range, sizeof(int)); if (NULL == count) { assert(0); return; } // 1. 先统计每个元素出现的次数 for (int i = 0; i < size; ++i) { count[array[i] - minValue]++; } // 2. 排序--按照计数数组的下标对数据进行回收 int index = 0; for (int i = 0; i < 10; ++i) { // 回收 while (count[i] > 0) { array[index++] = i + minValue;//展开 count[i]--; } } free(count); } int main() { int a[10] = { 4,1,3,2,7,6,5,9,10,8 }; printf("计数排序：n"); PrintArray(a, 10); CountSort2(a, 10); PrintArray(a, 10); return 0; }
