C++十種排序方法（快速排序、冒泡排序等等）
一、冒泡排序
1、概念及思路：冒泡排序顧名思義就是大的數沉下去，小的數浮上來，就跟氣泡在水底浮上來一樣；基本的思路很簡單，就是相鄰的兩個數相比較，如果前面那個數比后面那個數大，則換位置，否則不需要換，以此回圈下去（這里指的是從小到大排序，當然也可以從大到小）
2、代碼演示：
#include<iostream>
using namespace std;
int main() {
int i;
int arr[10] = { 1,5,2,3,6,8,7,9,4 ,0};//初始化陣列
for (int i = 0; i < 9;i++) {//一共回圈10次
for (int j = 0; j < 9-i; j++) {//執行的次數依次遞減
if (arr[j]>arr[j + 1]) {
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;//交換值
}
}
}
for (int j = 0; j < 10; j++)//列印陣列
{
cout << arr[j] << endl;
}
system("pause");
return 0;
}
二、選擇排序
1、思路：第一個數依次跟后面9個數比較，找出最小的那個數，放到前面來，在每次兩兩比較程序中，前面的數若比后面的數大，則交換其下標值，以此回圈9次就可以找出10個數中的最小那個，再那第二個數與后面8個數比較找出當中的最小值，以此類推…（這里也是以從小到大為例）
2、代碼演示：
#include<iostream>
using namespace std;
int main() {
int i;
int arr[10] ;//初始化陣列
for (i = 0; i < 10; i++)
{
cin >> arr[i];//輸入10要排序的數
}
for (int i = 0; i < 10;i++) {//一共回圈10次
for (int j = 0; j < 10; j++) {//找到10個數當中的最小值
if (arr[j]>arr[i ]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;//交換值
}
}
}
for (int j = 0; j < 10; j++)//列印陣列
{
cout << arr[j] << endl;
}
system("pause");
return 0;
}
三、插入排序
1、思路：從第二個數開始與第一個數比較，小的插入到前面，這樣就排好前面兩個數的位置了，第二次回圈，把第三個數與前面兩個數依次比較，如果小于第二個數的數，則把它插到第二個數的位置（實際上是交換兩個數的值），然后再與第一個數比較，如果小則插到第一個數的位置，這樣前面三個數就拍好的位置，以此類推，回圈兩次可以把前面三個數排好位置，回圈9次就可以把10個數的位置順序排好了，
2、代碼演示
#include<iostream>
using namespace std;
int main() {
int i;
int arr[10] ;//初始化陣列
for (i = 0; i < 10; i++)
{
cin >> arr[i];//輸入10要排序的數
}
for (int i = 1; i < 10;i++) {//10個數回圈9次
for (int j = i; j >0; j--) {//從第二個數開始與第一個數比較，小的插入到前面
if (arr[j-1]>arr[j]) {
int temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;//插到前面來（交換值）
}
}
}
for (int j = 0; j < 10; j++)//列印陣列
{
cout << arr[j] << endl;
}
system("pause");
return 0;
}
四、希爾排序
1、思路：首先定義一個gap,從第0個數開始，每隔一個gap取出一個數，將取出來的數進行比較，方法類似插入排序，第二輪從第二個數開始，每隔一個gap取出一個數再進行插入排序，四輪就可以取完（假如陣列有15個數），之后再將gap倍減，進行前面的步驟，直至gap為1.
2、代碼演示：
#include<iostream>
using namespace std;
int main() {
int i;
int arr[15] = {9,6,11,3,5,12,8,7,10,15,14,4,1,13,2};//初始化陣列
for (int gap = 4; gap > 0; gap /=2)//定義一個空隙為4，依次減倍
{
for (int i = gap; i < 15; i++) {
for (int j = i; j >gap - 1; j -= gap) {
//從第0個數開始，每隔4個數進行兩兩比較
if (arr[j - gap]>arr[j]) {
int temp = arr[j - gap];
arr[j - gap] = arr[j];
arr[j] = temp;//插到前面來（交換值）
}
}
}
}
for (int j = 0; j < 15; j++)//列印陣列
{
cout << arr[j] << endl;
}
system("pause");
return 0;
}
五、歸并排序
1、思路：設定一個中間值，把陣列分成兩組：第一組和第二組（假定兩組已排好序），然后定義一個全新的陣列，用來存放排好序的數，開始比較兩個陣列的數的大小，小的放全新陣列里面，第一個陣列跳到下一個位置，然后跟第二個陣列比較，小的繼續放全新的陣列里面，以此回圈下去，去到不符合條件為止（寫著程式里了）
2、代碼演示：
#include<iostream>
using namespace std;
int main() {
int arr[7] = {1,4,7,8,3,6,9};//初始化陣列
int mid = 7 / 2;//設定一個中間值，把陣列分成兩組（假定兩組已排好序）
//cout << mid << endl;
int i=0,j=mid+1, k=0;//設定三個變數，i,j表示兩組陣列的開始下標
int temp[7] = {};//定義一個全新的陣列，用來存放排好序的數
while (i <= mid&&j < 7) {//判斷i,j的值是否到達臨界
if (arr[i] < arr[j]) {
temp[k] = arr[i];
k++;
i++;
}
else {
temp[k] = arr[j];
k++;
j++;
}
}
while (i <= mid) temp[k++] = arr[i++];//補全另外兩種情況，未能同時滿足&&
while (j < 7) temp[k++] = arr[j++];
for (int k = 0; k < 7; k++)//列印陣列
{
cout << temp[k] << endl;
}
system("pause");
return 0;
}
六、快速排序
1、思路：快速排序和歸并排序一樣，都采用了分至和遞回的思想，首先選取一個數字pivot作為中心軸，然后把陣列中比pivot大的數放在pivot的右邊，比pivot小的事放在pivot的左邊，通過第一次排序就可以得到一個有順序的pivot，再將左子序列或者右子序列重復進行上面的操作，直至左子序列或者右子序列的數字為一，
2、代碼演示：
#include<iostream>
using namespace std;
void quickSort(int a[], int, int);//原型宣告
int main()
{
int array[] = { 32,64,12,43,69,5,78,10,3,70 },k;
int len = sizeof(array) / sizeof(int);//陣列長度
//cout << len << endl;
cout << "The orginal arrayare:" << endl;
for ( k = 0; k<len; k++)
cout << array[k] << " ";
cout << endl;
quickSort(array, 0, len - 1);
cout << "The sorted arrayare:" << endl;
for (k = 0; k<len; k++)
cout << array[k] << " ";//列印陣列
cout << endl;
system("pause");
return 0;
}
void quickSort(int s[], int l, int r)
{
if (l< r)
{
int i = l, j = r, x = s[l];
while (i < j)
{
while (i < j && s[j] >= x) // 從右向左找第一個小于x的數
j--;
if (i < j)
s[i++] = s[j];
while (i < j && s[i]< x) // 從左向右找第一個大于等于x的數
i++;
if (i < j)
s[j--] = s[i];
}
s[i] = x;
quickSort(s, l, i - 1); // 遞回呼叫
quickSort(s, i + 1, r);
}
}
七、計數排序
1、思路：基數排序是一種非比較排序，常用于規模大，數字種類小的排序中，如考試成績排名、人口年齡等等，思路很簡單，但實作起來不容易，首先得定義兩個陣列，一個用于存放數字種類的個數，另一個用于存放排好序的陣列，然后遍歷整個陣列，記錄下陣列中各數字的個數存放于第一個陣列中，比如1出現一次，就存放于temp[arr[1]]中，然后再將這些出現的個數一次存放在新的陣列中，從而達到排好序，
2、代碼演示：
#include<iostream>
using namespace std;
int arr[] = {3,2,3,1,5,6,8,6}, temp[1001], result[1001], n;
int main() {
int len = sizeof(arr)/sizeof(int);//陣列長度
cout << len << endl;
//cin >> n;
for (int i = 0; i < len; i++)
{
temp[arr[i]]++;
}
for (int i = 0; i < len; i++)
{
temp[i+1]+=temp[i];
}
for (int i = len - 1; i >= 0; i--)
{
result[--temp[arr[i]]] = arr[i];
}
for (int i = 0; i < len; i++)//列印陣列
{
cout << result[i] << " ";
}
system("pause");
return 0;
}
八、基數排序
1、思路：基數排序和計數排序一樣都是非比較排序，思路比較簡單，但是代碼實作還是有點難度的，假定一組數只有三位陣列成，先將個位上的數按順序好，如個位上是1就放在陣列index為1的陣列中；將個位上排好序之后，將數從上到下取出來（先進先出）進行十位上的排序，再進行百位上的排序，三輪排序之后就會呈現出一個有序的陣列，
2、代碼實作
#include <iostream>
using namespace std;
//列印陣列
void printArray(int array[], int length)
{
for (int i = 0; i < length; ++i)
{
cout << array[i] << " ";
}
cout << endl;
}
//求資料的最大位數,決定排序次數
int maxbit(int data[], int n)
{
int d = 1; //保存最大的位數
int p = 10;
for (int i = 0; i < n; ++i)
{
while (data[i] >= p)
{
p *= 10;
++d;
}
}
return d;
}
void radixsort(int data[], int n) //基數排序
{
int d = maxbit(data, n);
int temp[10];
int count[10]; //計數器
int i, j, k;
int radix = 1;
for (i = 1; i <= d; i++) //進行d次排序
{
for (j = 0; j < 10; j++)
count[j] = 0; //每次分配前清空計數器
for (j = 0; j < n; j++)
{
k = (data[j] / radix) % 10; //統計每個桶中的記錄數
count[k]++;
}
for (j = 1; j < 10; j++)
count[j] = count[j - 1] + count[j]; //將temp中的位置依次分配給每個桶
for (j = n - 1; j >= 0; j--) //將所有桶中記錄依次收集到temp中
{
k = (data[j] / radix) % 10;
temp[count[k] - 1] = data[j];
count[k]--;
}
for (j = 0; j < n; j++) //將臨時陣列的內容復制到data中
data[j] = temp[j];
radix = radix * 10;
}
}
int main()
{
int array[10] = { 73,22,93,43,55,14,28,65,39,81 };
radixsort(array, 10);
printArray(array, 10);
system("pause");
return 0;
}
九、堆排序
1、思路：步驟一：建立大根堆–將n個元素組成的無序序列構建一個大根堆，
步驟二：交換堆元素–交換堆尾元素和堆首元素，使堆尾元素為最大元素；
步驟三：重建大根堆–將前n-1個元素組成的無序序列調整為大根堆
2、代碼演示：`
#include<iostream>
using namespace std;
void adjust(int arr[], int len, int index)
{
int left = 2 * index + 1;
int right = 2 * index + 2;
int max = index;
if (left<len && arr[left] > arr[max]) max = left;
if (right<len && arr[right] > arr[max]) max = right; // max是3個數中最大數的下標
if (max != index) // 如果max的值有更新
{
swap(arr[max], arr[index]);
adjust(arr, len, max); // 遞回調整其他不滿足堆性質的部分
}
}
void heapSort(int arr[], int size)
{
for (int i = size / 2 - 1; i >= 0; i--) // 對每一個非葉結點進行堆調整(從最后一個非葉結點開始)
{
adjust(arr, size, i);
}
for (int i = size - 1; i >= 1; i--)
{
swap(arr[0], arr[i]); // 將當前最大的放置到陣列末尾
adjust(arr, i, 0); // 將未完成排序的部分繼續進行堆排序
}
}
int main()
{
int array[8] = { 6, 0, 15, 4, 21, 5, 7, 10 };
heapSort(array, 8);
for (auto it : array)
{
cout << it << endl;
}
system("pause");
return 0;
}
十、桶排序
略
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/276688.html
標籤：其他
下一篇：華碩Armoury crate 奧創控制中心 卡在安裝安裝已連接設備中，安裝失敗，請重新啟動，網路連接失敗（-101）