排序在很多场合中都经常用到,排序算法属于很常用的算法之一,在此对几种经典的排序算法进行简单的讲解,主要包括简单排序中的选择排序,冒泡排序,插入排序,以及快排,归并排序,希尔排序等。
1.选择排序选择排序的主要思想是先从所有的元素中选取一个最小的元素,与最左边的数进行位置交换,然后从第二个元素到最后一个元素中再取一个最小的元素,与左边第二个数进行交换,依次循环下去。
vectorSelect_Sort(vector nums) { int min_value = INT_MAX, min_index = 0; int len = nums.size(); for (int i = 0; i < len; i++) { min_value = INT_MAX; for (int j = i; j < len; j++) { if (nums[j] < min_value) { min_value = nums[j];//记录最小值 min_index = j;//记录最小值的位置 } } swap(nums[i], nums[min_index]);//将最小值移至左边 } return nums; }
时间复杂度:O(n^2),空间复杂度:O(1)
2. 冒泡排序类似于冒泡的原理,将一个元素与后续元素依次作比较,若满足条件则进行位置交换,使得该元素逐渐向后移。
vectorBubble_Sort(vector nums) { int len = nums.size(); for (int i = nums.size()-1; i>0; i--) { for (int j = 0; j nums[j+1])swap(nums[j], nums[j+1]); } } return nums; }
时间复杂度:O(n^2),空间复杂度:O(1)
3.插入排序插入排序的思想是不断使前面一部分元素保持有序状态。假定前a个元素为有序状态,需要插入第a+1个元素,将第a+1个元素依次与前a个元素进行比较,并在合适的位置的进行插入,使a+1个元素保持有序。
vectorInsert_Sort(vector nums) { int len = nums.size(); for (int i =1; i< nums.size() ; i++) { for (int j = i; j>0; j--) { if (nums[j] < nums[j - 1])swap(nums[j], nums[j - 1]); } } return nums; }
时间复杂度:O(n^2),空间复杂度:O(1)
4. 归并排序归并排序用到了递归及合并两个 *** 作,合并 *** 作主要是将左右两边均有序的数组变成一个有序的数组,而递归 *** 作是不断重复上述过程,不断合并数组,最终使所有元素变成有序。
void Merge(vector&nums, int leftptr, int rightptr, int rightbound) { vector temp(rightbound - leftptr + 1, 0); int i = leftptr, j = rightptr, k = 0; int mid = rightptr - 1; while (i <= mid && j <= rightbound) { temp[k++] = nums[i] < nums[j] ? nums[i++]:nums[j++]; } while (i <= mid)temp[k++] = nums[i++]; while (j <= rightbound)temp[k++] = nums[j++]; //将排好序的元素放入nums中 for (int m = 0; m < temp.size(); m++) { nums[m + leftptr] = temp[m]; } } void TS(vector &nums, int left, int right) { //递归终止条件 if (left == right)return; //对序列进行切分 int mid = left + (right - left) / 2; //对左边进行排序 TS(nums,left, mid); //对右边进行排序 TS(nums, mid + 1, right); //对排好序的左右两边进行合并 Merge(nums,left,mid+1,right); } vector MergetSort(vector &nums) { TS(nums, 0, nums.size()-1); return nums; }
时间复杂度:O(n*log(n)) 空间复杂度:O(n)
5.希尔排序是优化的选择排序,每取一个间隔gap的所有元素进行排序
vectorShell_Sort(vector nums) { //选择最优gap长度 int h = 1; while (h <= nums.size() / 3) { h = h * 3 + 1; } for (int gap = h; gap > 0; gap =(gap-1)/3) { for (int i = gap; i < nums.size(); i++) { for (int j = i; j > gap-1; j -= gap) { if (nums[j] < nums[j - gap])swap(nums[j], nums[j - gap]); } } } return nums; }
时间复杂度:O(n^1.3) 空间复杂度:O(1)
6. 单轴快排int get_pivot(vector& nums, int left,int right) { int pivot = right; int i = left, j = right - 1; while (i <= j) { while (i <= j && nums[i] <= nums[pivot])i++; while (i <= j && nums[j] > nums[pivot])j--; if (i <= j)swap(nums[i++], nums[j--]); } swap(nums[i], nums[pivot]); return i; } void Sort(vector & nums,int left,int right) { if (left >= right)return; int rand_position = left + rand() % (right - left); swap(nums[rand_position], nums[right]); int pivot = get_pivot(nums, left, right); Sort(nums, left, pivot - 1); Sort(nums, pivot + 1, right); } vector QuickSort(vector &nums) { Sort(nums,0, nums.size() - 1); return nums; }
时间复杂度:O(n*log(n)) 空间复杂度:O(log(n))
7.使用对数器进行算法验证#include#include //要使用vector必须包含vector头文件 #include //产生随机数的rand包含在此头文件中 #include using namespace std; //data_cheker对数器 vector Generation() { int len = 1000; vector nums; for (int i = 0; i < len; i++) { nums.push_back(rand()); } return nums; } int main() { int times = 1000; bool result = true; while (times > 0) { vector nums1 = Generation(); vector nums2 = nums1; sort(nums1.begin(), nums1.end()); nums2 = QuickSort(nums2);//修改相应的排序算法名称即可 for (int i = 0; i < nums2.size(); i++) { if (nums1[i] != nums2[i]) { result = false; break; } } if (result == false)break; times--; } if (result == false)cout << "算法不正确" << endl; else cout << "测试案例全部通过。" << endl; return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)