快捷導(dǎo)航

c++數(shù)組排序的5種方法實(shí)例代碼

更新時(shí)間：2023年01月11日 14:13:42 作者：布魯擼代碼

大家還在為大小排序而煩惱嗎?今天讓我我大家解決這個(gè)問題吧,下面這篇文章主要給大家介紹了關(guān)于c++數(shù)組排序的5種方法,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下

方法一：冒泡排序

比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
對(duì)每一對(duì)相鄰元素做同樣的工作，執(zhí)行完畢后，找到第一個(gè)最大值。
重復(fù)以上的步驟，每次比較次數(shù)-1，直到不需要比較

示例：對(duì)數(shù)組4,2,8,0,5,7,1,3,9 進(jìn)行排序

#include<iostream>
 
using namespace std;
 
int main() {
 
	int arr[9] = { 4,2,8,0,5,7,1,3,9 };
 
	for (int i = 0; i < 9 - 1; i++)
	{
		for (int j = 0; j < 9 - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
 
	for (int i = 0; i < 9; i++)
	{
		cout << arr[i] << endl;
	}
    
	system("pause");
 
	return 0;
}

方法二：sort函數(shù)排序

示例：對(duì)數(shù)組2,4,5,3,1進(jìn)行排序

sort函數(shù)的算法效率相當(dāng)于快排。

sort 函數(shù)默認(rèn)的是進(jìn)行升序排序

有兩種方法可以進(jìn)行降序，可自由選擇

1. 使用greater<int>()

如果排序其他類型可更改參數(shù)

2. 自定義一個(gè)比較大小的函數(shù)，將大的排在前面

方法三：用交換函數(shù)swap排序

… …

if(a>b) swap(a,b);

if(a>c) swap(a,c);

if(b>c) swap(b,c);

… …

方法四：快速排序

找到分界點(diǎn)x，q[L]，q[(L+R)/2]，q[R]
左邊所有數(shù)Left<=x，右邊所有數(shù)Right>=x
遞歸排序Left，遞歸排序Right

快速排序算法模板：

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    
    int i = l - 1, j = r + 1, x = q[l+r>>1]; //l+r>>1的意思是l+r的值除以2取整
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
        else break;
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

方法五：歸并排序

確定分界點(diǎn)：mid=(l+r)/2
遞歸排序Left，遞歸排序Right
歸并 —— 合二為一

歸并排序算法模板

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;
    
    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] < q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
    
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];
    
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}