当前位置：首页 > news >正文

交换排序、归并排序、计数排序

news 2025/7/27 12:44:14

冒泡排序：

void BubbleSort(int* a, int n)
{//第一层循环是趟数，第二层是交换for (int i = 0; i <= n-2; i++){int flag = 0;for (int j = 0; j <= n - 2 - i; j++){if (a[j] > a[j + 1]){swap(&a[j], &a[j + 1]);flag = 1;}}if (flag == 0){break;}
}
}

这里做了一个小优化，通过flag的值来减少运行趟数，防止已经有序的情况下继续比较，最坏时间复杂度N方，最好时间复杂度o(N) ，具有稳定性

快速排序：

void _QuickSort1(int* a, int left, int right)
{int key = left; int begin = left, end = right;if (begin >=end){return;}三数取中法//int mid =Getmid(a, left, right);//swap(&a[left], &a[mid]);//随机数法//int randi = rand() % (right - left) + left;//swap(&a[randi], &a[left]);while (begin<end){while (begin<end){if (a[key] <= a[end])//一定保证右边先走{end--;}else{break;}}while (begin<end){if (a[key] >=a[begin]){begin++;}else{break;}}swap(&a[begin], &a[end]);}swap(&a[left], &a[begin]);key = begin;_QuickSort1(a, 0, key - 1);_QuickSort1(a, key + 1, right);
}

快排时间复杂度是o(nlogn),但是当整个数组为有序序列时，快排时间复杂度就为N方，所以这里有三数取中法和随机数法，使key的值变得随机，这里更推荐三数取中，因为交换后所得到的值肯定为中间值，但有一种特殊情况，就是整个数列中的数都为同一个值，这时候时间复杂度只能为N方,具有不稳定性

三数取中法

int Getmid(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] > a[mid]){if (a[mid] > a[right]) {return mid;}else if (a[left] > a[right]){return right;}else{return left;}}else{if (a[left] > a[right]){return left;}else if (a[right] < a[mid]){return right;}else{return mid;}}
}

随机数法

//随机数法//int randi = rand() % (right - left) + left;

快排双指针法：

void _QuickSort2(int* a, int left, int right)
{if (left >= right){return;}int key = left;int prev = left;int cur = left+1;while (cur <= right){if (a[cur] < a[key] && ++prev != cur){swap(&a[prev], &a[cur]);}cur++;}swap(&a[key], &a[prev]);key = prev;_QuickSort2(a, 0, key - 1);_QuickSort2(a, key + 1, right);
}

相比最原始的快排更好理解，代码量也少

快排非递归

void _QuickSort(int* a, int n)
{ST st;STInit(&st);STPush(&st, n-1);STPush(&st, 0);while (!STEmpty(&st)){int left = STTop(&st);STPop(&st);int right = STTop(&st);STPop(&st);int key = left;int prev = left;int cur = left + 1;while (cur <= right){if (a[cur] < a[key] && ++prev != cur){swap(&a[prev], &a[cur]);}cur++;}swap(&a[key], &a[prev]);key = prev;if ((key+1)<right){STPush(&st, right);STPush(&st, key + 1);}if (left<(key-1)){STPush(&st, key - 1);STPush(&st, left);}}STDestroy(&st);
}

当递归次数太多时会建立大量函数栈帧，所以在这里实现快排的非递归排序，这里用到了栈的知识，模拟了快排的递归过程，类似于二叉树的前序遍历，运用队列也可以实现，但队列是模拟了二叉树的层序遍历，快排的本质还是前序遍历

归并排序：

void _MergeSort(int* a, int left, int right,int*tem)
{if (left>= right){return;}int mid = (left + right) / 2;int begin1 = left;int end1 = mid;int begin2 = mid + 1;int end2 = right;_MergeSort(a, left, mid, tem);_MergeSort(a, mid + 1, right, tem);int i = begin1;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tem[i++]=a[begin1++];}else{tem[i++] = a[begin2++];}}while (begin1 <= end1){tem[i++] = a[begin1++];}while (begin2 <= end2){tem[i++] = a[begin2++];}memcpy(a + left, tem + left,sizeof(int)*( right - left + 1));
}

时间复杂度nlogn,具有稳定性

归并排序的非递归

void _MergeSort1(int* a, int n)
{int* tem = (int*)malloc(sizeof(int) * n);if (tem == NULL){perror("malloc fail");return;}int gap = 1;//gap是每组长度，长度等于n的时候不用归并，理解本质while (gap < n){for (int i = 0; i <n; i+=2*gap){int left = i;int right = i + 2 * gap - 1;int begin1 = i;int end1 = i + gap - 1;int begin2 = end1 + 1;int end2 = begin2 + gap - 1;int j = begin1;if (end1 >= n-1 || begin2 >= n){break;}if (end2 >=n){end2 = n - 1;}while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tem[j++] = a[begin1++];}else{tem[j++] = a[begin2++];}}while (begin1 <= end1){tem[j++] = a[begin1++];}while (begin2 <= end2){tem[j++] = a[begin2++];}memcpy(a + left, tem + left, sizeof(int) * (end2 - left + 1));//end2可能会变，这里不能用right减}gap *= 2;}free(tem);tem = NULL;
}

计数排序

void CountSort(int* a, int n)
{int min = a[0], max =a[ 0];for (int i = 1; i < n; i++){if (a[i] < min)min = a[i];if (a[i] > max)max = a[i];}int range = max - min + 1;int* count = (int*)calloc(sizeof(int),range);if (count == NULL){return;}for (int i = 0; i < n; i++){count[a[i]-min]++;//出现几次}int j = 0;for (int i = 0; i < range; i++){while (count[i]--){a[j++] = i + min;}}
}