用c语言实现各种排序算法

#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> void MyPrint(int* a, int size) { for (int i = 0; i < size; i++) { printf("%d ", a[i]); } printf("\n"); } //三数取中 int takeMiddle(int *a,int left,int right) { int mid = left + (right - left) / 2; // 防止溢出 if (a[left] > a[mid]) { if (a[mid] > a[right]) { return right; } else if (a[left] < a[right]) { return left; } else { return mid; } } else { if (a[mid] < a[right]) { return mid; } else if (a[left] > a[right]) { return right; } else { return left; } } } void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } //坑位法（快速排序）//思路 void QuickSort_test(int* a, int size) { //设计单趟排序 int begin = 0; int end = size - 1; int pivot = begin; int key = a[begin]; while (begin < end) { while (begin < end && a[end] > key) { end--; } a[pivot] = a[end]; pivot = end; while (begin < end && a[begin] < key) { begin++; } a[pivot] = a[begin]; pivot = begin; } a[begin] = key; } //坑位法（快速排序）//最终（递归法） void QuickSort(int* a, int left, int right) { //递归的结束条件 if (left >= right) { return; } int keysub = takeMiddle(a, left, right); swap(&a[left], &a[keysub]); int begin = left; int end = right; int pivot = begin; int key = a[begin]; while (begin < end) { //单趟 while (begin < end && a[end] > key) { end--; } a[pivot] = a[end]; pivot = end; while (begin < end && a[begin] < key) { begin++; } a[pivot] = a[begin]; pivot = begin; } pivot = begin; a[begin] = key; //递归，分治 QuickSort(a, left, pivot - 1); QuickSort(a, pivot + 1, right); } //双指针法 void QuickSort2(int *a,int left,int right) { //递归的结束条件 if (left >= right) { return; } int begin = left; int end = right; int key = a[begin]; int keyi = begin; while (begin < end) { while (begin < end && a[end] >= key) { end--; } while (begin<end && a[begin]<=key) { begin++; } swap(&a[begin], &a[end]); } swap(&a[begin], &a[keyi]); QuickSort2(a, left,begin - 1); QuickSort2(a, begin + 1, right); } //前后指针法 void QuickSort3(int* a, int left, int right) { //递归的结束条件 if (left >= right) { return; } int prev = left; int cur = left + 1; int key = left; while (cur <= right) { if (a[cur] < a[key]) { ++prev; swap(&a[cur], &a[prev]); } cur++; } swap(&a[key],& a[prev]); QuickSort3(a, left, prev - 1); QuickSort3(a, prev + 1, right); } //前后指针法优化 void QuickSort3_1(int* a, int left, int right) { //递归的结束条件 if (left >= right) { return; } int prev = left; int cur = left + 1; int key = left; while (cur <= right) { if (a[cur] < a[key]&&++prev!=cur) { //自己和自己就没必要交换了 swap(&a[cur], &a[prev]); } cur++; } swap(&a[key], &a[prev]); QuickSort3(a, left, prev - 1); QuickSort3(a, prev + 1, right); } void test() { int arr[] = { 6,1,2,7,9,3,4,5,10,8 }; int size = sizeof(arr) / sizeof(arr[0]); //QuickSort(arr, 0, size - 1); //QuickSort2(arr, 0, size - 1); QuickSort3(arr, 0, size - 1); MyPrint(arr, size); } int main() { test(); return 0; }