赞
踩
冒泡排序应该是最先学到的一种排序算法,也是最简单的一种排序算法。
思路就是,从最前面开始两两比较大的放后面。但是要注意一个问题每走一趟就把这趟最大的放后面了,所以要控制一下单趟和多趟。这里用两个循环解决。
//冒泡排序 void BubbleSort(int* a, int n) { for (int j = 0; j < n; j++) { // 单趟 int flag = 0; for (int i = 1; i < n - j; i++) { if (a[i - 1] > a[i]) { swap(&a[i - 1], &a[i]); flag = 1; } } if (flag == 0) { break; } } }
时间复杂度:最坏情况:O(N^2)
最好情况:O(N)
空间复杂度:O(1)
先思考单趟,设定end位置的下一个位置为tmp,并把tmp位置的值用一个临时变量存起来。然后进入循环,如果tmp的值小于end位置的值就让end位置的值覆盖end+1位置的值,让end的值往后走,end下标位置–。如果tmp位置的值大于end位置的值就把tmp位置的值放入end位置的后面,这里的循环判断条件是end>0。这是单趟的思路,然后用for循环让end从下标为0位置开始,用这个单趟的思路走多趟进行排序。
//插入排序 void InsertSort(int* a, int n) { for (int i = 0; i < n - 1; i++) { int end = i; int tmp = a[end + 1]; while (end > 0) { if (tmp < a[end]) { a[end + 1] = a[end]; end--; } else { break; } } a[end + 1] = tmp; } }
时间复杂度:最坏情况下为O(NN),此时待排序列为逆序,或者说接近逆序
最好情况下为O(N),此时待排序列为升序,或者说接近升序。
空间复杂度:O(1)*
希尔排序跟插入排序有异曲同工之处,但是希尔排序是对插入排序的优化,在希尔排序中用到了gap,gap值随着排序的进行会减小当gap>1时都是预排序。当gap==1时数组就接近有序了,然后在对这个序列进行一次插入排序这时排序就很快了。
每次走gap步其他和插入排序思路一样。要注意一下i的范围的取值,i要小于n-gap,如果i超过了n-gap走到了n-gap后面的位置i再加gap的话就越界了。i++多组并行走gap步优化预处理的过程。随着gap值的变化gap会越来越小,gap为1时预处理完毕,其实gap为1时就相当于插入排序。
//希尔排序 void ShellSort(int* a, int n) { int gap = n; while (gap > 0) { gap = gap / 3 + 1; } //进入循环多组并行 for (int i = 0; i < n - gap; i++) { int end = i; int tmp = i + gap; while (end > 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end--; } else { break; } } a[end + gap] = tmp; } }
时间复杂度:O(n^(1.3-2))
定义begin位置也就是下标为0位置为最大和最小位置。从begin+1位置开始遍历数组,如果有值大于maxi位置的值,就赋这个位置下标为最大位置。如果有值小于mini位置的值,就赋这个位置下标为最小位置。然后把最大值与之前end位置的值交换位置,最小位置的值与之前begin位置的值交换位置。这次交换完之后,因为while循环判断条件是begin<end继续重复上面步骤。
//选择排序 void SelecSort(int* a, int n) { int begin = 0; int end = n - 1; while (begin < end) { int maxi = begin; int mini = begin; for (int i = begin + 1; i < n; i++) { while (a[i] > a[maxi]) { maxi = i; } while (a[i] < a[mini]) { mini = i; } } swap(&a[begin], &a[mini]); if (begin == maxi) { maxi = mini; } swap(&a[end], &a[maxi]); begin++; end--; } }
时间复杂度为O(n^2)
堆排在之前二叉树中的文章中有具体实现步骤,下面是二叉树的文章:
添加链接描述
//向上调整建堆 void AdjustDown(int* a, int n, int parent) { // 先假设左孩子小 int child = parent * 2 + 1; while (child < n) // child >= n说明孩子不存在,调整到叶子了 { // 找出小的那个孩子 if (child + 1 < n && a[child + 1] > a[child]) { ++child; } if (a[child] > a[parent]) { swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } //堆排 void HeapSort(int* a, int n) { // 向下调整建堆 O(N) for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, n, i); } // O(N*logN) int end = n - 1; while (end > 0) { swap(&a[0], &a[end]); AdjustDown(a, end, 0); --end; } }
选出一个key作为其他值比较的值,一般是最左边或者最右边的值。把最左边的下标和最右边的下标定义为begin和end。左边找大于key的值右边找小于key的值。然后让左边找到的值与右边找到的值交换位置,如果不大于key的值或者不小于key的值左边继续往右走右边继续往左走。当begin和end相遇的时候,把相遇位置的值与key位置的值交换位置。然后把key的位置换到begin和end相遇位置,这样这个区间就成[left,key1]key[key+1,right]。接着让左区间和右区间继续递归。
void QuickSort1(int* a, int left, int right) { if (left >= right) { return; } int keyi = left; int begin = left; int end = right; while (begin < end) { //右边找小 while (begin<end && a[end] > a[keyi]) { end--; } //左边找大 while (begin < end && a[begin] < a[keyi]) { begin++; } swap(&a[begin], &a[end]); } //把keyi位置换到中间 swap(&a[keyi], &a[end]); keyi = begin; //递归接着进行排序 QuickSort1(a, left, keyi - 1); QuickSort1(a, keyi + 1, right); } }
如果这个要排序的数组非常长,end要找比key小的但这个数组是升序的。end就得从这个数组的最右边走很长一段距离才能找到小。这时我们可以用三数取中来优化算法。
三数取中就是找到left的值和right的值和left和它俩中间的值,比较谁是中间值。中间值的当key。
//三数取中 int GetMidi(int* a, int left, int right) { int midi = (left + right) / 2; if (a[left] < a[midi]) { if (a[midi] < a[right]) { return midi; } else if (a[left] < a[right]) { return right; } else { //a[left]>a[right] return left; } } else //(a[left]>a[midi]) { if (a[right] < a[midi]) { return midi; } else if (a[left] < a[right]) { return left; } else { return right; } } }
小区间优化:
这里这个递归是和而二叉树类似的,最下面一层的值占整个二叉树的%50,有好多就浪费掉了。当我们递归到一定程度时,可以采用插入排序来进行优化。
if ((right - left + 1) < 5)
{
InsertSort(a + left, right - left + 1);
}
优化后代码:
void QuickSort1(int* a, int left, int right) { if (left >= right) { return; } if ((right - left + 1) < 5) { InsertSort(a + left, right - left + 1); } else { //三数取中 int midi = GetMidi(a, left, right); swap(&a[left], &a[midi]); int keyi = left; int begin = left; int end = right; while (begin < end) { //右边找小 while (begin<end && a[end] > a[keyi]) { end--; } //左边找大 while (begin < end && a[begin] < a[keyi]) { begin++; } swap(&a[begin], &a[end]); } //把keyi位置换到中间 swap(&a[keyi], &a[end]); keyi = begin; //递归接着进行排序 QuickSort1(a, left, keyi - 1); QuickSort1(a, keyi + 1, right); } }
选出一个key,一般是最左边或是最右边的。prev指针指向序列开头,cur指针指向prev+1。若cur指向的内容小于key,则prev先向后移动一位,然后交换prev和cur指针指向的内容,然后cur指针++;若cur指向的内容大于key,则cur指针直接++。如此进行下去,直到cur到达end位置,此时将key和++prev指针指向的内容交换即可。经过一次单趟排序,最终也能使得key左边的数据全部都小于key,key右边的数据全部都大于key。
然后也还是将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作
int QuickSort2(int* a, int left, int right) { int key = left; int mind = GetMidi(a, left, right); swap(&a[mind], &a[left]); int prev = left; int cur = prev + 1; while (cur <= right) { if (a[cur] < a[key] && ++prev != cur) swap(&a[prev], &a[cur]); cur++; } swap(&a[key], &a[prev]); QuickSort2(arr, begin, keyi - 1); QuickSort2(arr, keyi + 1, end); }
把区间放入栈中,注意栈是先进后出所以先入right后入left。然后取出这个区间进行进行排序,找到key的位置。[left,key-1]key[key+1,right],让右区间入栈然后让左区间入栈,取出左区间进行排序找到新的key然后重复上述过程,类似递归的思想。左区间完了搞右区间。
int QuickSort2(int* a, int left, int right) { int key = left; int mind = GetMidi(a, left, right); swap(&a[mind], &a[left]); int prev = left; int cur = prev + 1; while (cur <= right) { if (a[cur] < a[key] && ++prev != cur) swap(&a[prev], &a[cur]); cur++; } swap(&a[key], &a[prev]); return prev; }
#include"Stack.h" //用栈实现快排 void QuickSortNonR(int* a, int left, int right) { ST st; STInit(&st); STPush(&st, right);//9 STPush(&st, left);//0 while (!STEmpty(&st)) { int begin = STTop(&st); STPop(&st);//0 int end = STTop(&st); STPop(&st);//9 //[left,key-1]key[key+1,right] int key = QuickSort2(a, begin, end); if (key + 1 < right) { STPush(&st, right); STPush(&st, key + 1); } if (left < key + 1) { STPush(&st, key + 1); STPush(&st, left); } } STDestroy(&st); }
创建一个tmp数组,把之后归并的数据先放入这个tmp数组中然后再放入原数组中。把begin到end区间找中间值分割开来。int mid = (begin + end) / 2; //[begin,mid][mid+1,end]。
然后让两个数组进行比较,小的放到tmp数组中。有可能其中一个数组比较完之后另一个还有值,所以得判断一下,把剩余的值放入tmp中。
这个也需要递归。
//归并排序 void _MergeSort(int* a, int* tmp, int begin, int end) { if (begin >= end) return; int mid = (begin + end) / 2; //[begin,mid][mid+1,end] _MergeSort(a, tmp, begin, mid); _MergeSort(a, tmp, mid + 1, end); int begin1 = begin; int end1 = mid; int begin2 = mid + 1; int end2 = end; int i = begin; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[i++] = a[begin1++]; } else { tmp[i++] = a[begin2++]; } } while (begin1 <= end1) { tmp[i++] = a[begin1++]; } while (begin2 <= end2) { tmp[i++] = a[begin2++]; } memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int)); } void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc error"); return; } _MergeSort(a, tmp, 0, n - 1); free(tmp); tmp == NULL; }
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); return; } // gap每组归并数据的数据个数 int gap = 1; while (gap < n) { for (int i = 0; i < n; i += 2 * gap) { // [begin1, end1][begin2, end2] int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; // 第二组都越界不存在,这一组就不需要归并 if (begin2 >= n) break; // 第二的组begin2没越界,end2越界了,需要修正一下,继续归并 if (end2 >= n) end2 = n - 1; int j = i; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[j++] = a[begin1++]; } else { tmp[j++] = a[begin2++]; } } while (begin1 <= end1) { tmp[j++] = a[begin1++]; } while (begin2 <= end2) { tmp[j++] = a[begin2++]; } memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1)); } printf("\n"); gap *= 2; } free(tmp); tmp = NULL; }
这里先一一归并然后两两归并然后四四归并,依此类推。gap每组表示归并数据的个数,比方说这个gap组中有两个值,就是这两个值进行归并,这gap组中有四个值,就两两归并。i代表每组的归并的起始位置。每循环一次就要让gap*2,这样才能满足每组归并数据的个数。
这里有一个问题需要注意:
第二组都越界不存在,这一组就不需要归并
if (begin2 >= n)
break;
第二的组begin2没越界,end2越界了,需要修正一下,继续归并
if (end2 >= n)
end2 = n - 1;
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。