html5网站建设平台/佛山本地网站建设

快速排序

/*
算法思想：在参加排序的序列中任意选择一个元素（通常称为分界元素或基准元素），把小于或等于
分界元素的所有元素都移到分界元素的前面，把大于分界元素的所有元素都移到分界元素的后面，
这样，当前参加排序的序列就被划分成前后两个子序列，其中前一个子序列中的所有元素都小于后
一个子序列的所有元素，并且分界元素正好处于排序的最终位置上。然后分别对这两个子序列递归
地进行上述排序过程，直到所有元素都处于排序的最终位置上，排序结束。
*/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;//输出结果 
void printData(vector<int> a);//将 pivot左边的数都小于他，右边的数都大于他 
int Partition(vector<int>& a, int low, int high)
{int pivot;//其实为了方便直接用第一个数做枢纽值很不好 pivot = a[low];//从线性表的两端交替地向中间扫描while (low < high){while (low < high && a[high] >= pivot) high--;//比枢纽值小，就把他放到枢纽值左边 a[low] = a[high];while (low < high && a[low] <= pivot) low++;//比枢纽值大，就把他放到枢纽值右边 a[high] = a[low];} // 此时, pivot左边的数据都小于他，右边的数据都大于他 a[low] = pivot;//返回枢纽值位置 return low;
}void Qsort(vector<int>& a, int low, int high)
{int pivotloc; if (low < high){//设置pivot值,然后排序, 使得 pivot左边的数都小于他，pivot右边的数都大于他, //返回排序后pivot的位置 pivotloc, 然后再对其 两边的数据 递归排序 pivotloc = Partition(a, low, high);    //枢纽值(pivot)左边的数都小于 pivot, 排序所有小于pivot的值 Qsort(a, low, pivotloc - 1); //pivot右边的数都大于pivot, 排序所有大于pivot的值 Qsort(a, pivotloc + 1, high);} 
}//启动程序 
void QuickSort(vector<int>& a, int size)
{//设置排序的区间 Qsort(a, 0, size - 1);printData(a);
}void printData(vector<int> a)
{for (const auto& e : a) {cout << e << " ";}cout << endl;
}int main()
{vector<int> a = {-1, 2, 5, 6, 3, 10, 8, 20, 15, 12, 44, 23, 34};unsigned n = a.size();//插入排序 
    QuickSort(a, n);return 0;
}

堆排序

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;void printData(vector<int> a)
{for (const auto& e : a) {cout << e << " ";}cout << endl;
}//调整为大顶堆 
void HeapAdjust(vector<int>& a, int low, int high)
{int child;int tmp;//tmp: 父亲结点; 左结点的索引 < n ; 继续 判断孩子结点  // 2 * i : 获得左孩子结点索引 for (tmp = a[low]; low * 2 < high; low = child){child = low * 2;    //获得左孩子结点索引 //如果孩子结点索引 尚未越界, 且  左孩子结点 小于 右孩子 结点    //就获得右孩子结点索引 if (child != high - 1 && a[child] < a[child + 1]) {child++;}if (tmp < a[child]) {      //父亲 < 孩子 a[low] = a[child];     //孩子 替换 父亲结点 
        }else {break;}} a[low] = tmp;     //将父亲结点 插入 到比他大的 孩子结点位置.
    
}//没有使用传引用，不改变 a 
void HeapSort(vector<int>& a, int n)
{//建立大顶堆for (int i = n / 2; i >= 0; i--){HeapAdjust(a, i, n);    }for (int j = n - 1; j > 0; j--){swap(a[0], a[j]);//将 a[1..i] 重新调整为大顶堆HeapAdjust(a, 0, j); }printData(a);
}int main()
{vector<int> a = {-1, 2, 5, 6, 3, 10, 8, 20, 15, 12, 44, 23, 34};unsigned n = a.size();//插入排序 
    HeapSort(a, n);return 0;
}

不懂可以看这个： https://www.cnblogs.com/0zcl/p/6737944.html

归并排序

#include <iostream>
#include <cstring>
using namespace std;int test[100] = { 0 };void Merge(int *test, int lo, int mid, int hi); 
void MergeSort(int *test, int lo, int hi) {if (hi - lo < 2) return;int mid = (lo + hi) >> 1;MergeSort(test, lo, mid);                           //对前半段排序MergeSort(test, mid, hi);                           //对后半段排序Merge(test, lo, mid, hi);                           //归并
}//归并---O(nlogn), T(n) = 2T(n/2) + O(n)
void Merge(int *test, int lo, int mid, int hi) {//A用来存放合并后的向量，B，C进行比较(前后子向量比较)int  *A = test + lo;          //合并后的向量A[0,hi-lo) = int s[lo,hi)int lb = mid - lo;int  *B = new int [lb];        //前子向量 B[0,lb) = int s[lo,mi)for (int i = 0; i < lb; B[i] = A[i++]);   //复制前子向量int lc = hi - mid;int  *C = test + mid;         //后子向量for (int i = 0, j = 0, k = 0; (j < lb || k < lc);) {//B[i], C[k]中小者转至A的末尾.        //因为C本来就占据A中，不需要考虑提前耗尽情况if ((j < lb) && (k >= lc || C[k] >= B[j]))      //C[k]已无或不小A[i++] = B[j++];if ((k < lc) && (j >= lb || B[j] >= C[k]))      //B[k]已无或不小A[i++] = C[k++];}delete[]B;
}int main()
{//用来测试 非模板写的 归并排序 算法int Test[13] = { 1, 5, 2, 3, 6, 8, 9, 10, 13, 12, 4, 7, 11 };MergeSort(Test, 0, 13);for (int i = 0; i < 13; i++)cout << Test[i] << " ";cout << endl;return 0;}

插入排序

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;void printData(vector<int> a)
{for (const auto& e : a) {cout << e << " ";}cout << endl;
}//没有使用传引用，不改变 a 
void InsertSort(vector<int> a, int n)
{for (int i = 1; i < n; i++){if (a[i] < a[i - 1])  //当前选择的数 < 前一个数 {                     //就把放到前面去 int    j = i - 1;int temp = a[i];//当前的数跟前面数比较, 一直小，前面的数就一直后移 while (j >= 0 && temp < a[j]){a[j + 1] = a[j];j--;}a[j + 1] = temp; }}printData(a);
}//折半插入排序, 只是使用折半查找的方法来寻找插入位置
void BinInsertSort(vector<int> a, int n)
{int low, high, mid, tmp;for (int i = 1; i < n; i++)    {tmp = a[i];low = 0, high = i - 1;while (low <= high){mid = (low + high) / 2;if (tmp > a[mid]) {low = mid + 1;}else {high = mid - 1;}}for (int j = i; j > low; j--) {a[j] = a[j - 1];          //前移 
        }a[low] = tmp;}printData(a);
} int main()
{vector<int> a = {-1, 2, 5, 6, 3, 10, 8, 20, 15, 12};unsigned n = a.size();//插入排序 
    InsertSort(a, n);//折半插入排序
    BinInsertSort(a, n);return 0;
}

选择排序

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;void printData(vector<int> a)
{for (const auto& e : a) {cout << e << " ";}cout << endl;
}//没有使用传引用，不改变 a 
void ChooseSort(vector<int> a, int size)
{int min = 0, i, j;for (i = 0; i < size - 1; i++){min = i;              //此假设为最小值的下标for (j = min + 1; j < size; j++){if (a[min] > a[j]) {min = j;      //找出当前位置 最小值的下标 
            }} //如果假设的最小的下标改变了，就将最小下标位置元素//与 i 位置交换，则 i 为当前位置最小的元素if (i != min) {swap(a[i], a[min]);}}printData(a);
}int main()
{vector<int> a = {-1, 2, 5, 6, 3, 10, 8, 20, 15, 12, 44, 23, 34};unsigned n = a.size();//插入排序 
    ChooseSort(a, n);return 0;
}

冒泡排序

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;void printData(vector<int> a)
{for (const auto& e : a) {cout << e << " ";}cout << endl;
}//没有使用传引用，不改变 a 
void BubbleSort(vector<int> a, int n)
{bool ordered;//外层循环 -- 一共进行比较的趟数( n - 1 ) for (int i = 0; i < n - 1; i++){ordered = true;//每趟需要比较的次数 //每次循环后，可以依次得到Max，次Max, 次次max...... for (int j = 0; j < n - i - 1; j++){//每次选出  当前位置元素  应当所在的  最大位置, 并交换if (a[j] > a[j + 1]) {swap(a[j], a[j + 1]);//只要交换，则说明交换前，不是有序ordered = false;}}//一次交换都没有，说明已经没有逆序对，则已经有序，直接退出循环！ if (ordered) {break;}}printData(a);
}int main()
{vector<int> a = {-1, 2, 5, 6, 3, 10, 8, 20, 15, 12};unsigned n = a.size();//插入排序 
    BubbleSort(a, n);return 0;
}