當(dāng)前位置：首頁(yè) > 编程资源 > 编程问答 >内容正文

编程问答

排序算法比较总结

發(fā)布時(shí)間：2023/12/9 编程问答 24 豆豆

生活随笔收集整理的這篇文章主要介紹了排序算法比较总结小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

冒泡排序

每次從頭開(kāi)始（每次結(jié)束可以不到最后，因?yàn)樯弦淮我呀?jīng)確定最大值在末尾了），比較相鄰兩個(gè)數(shù)，每次下沉一個(gè)最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include?<iostream>
using?namespace std;
?
void?bubbleSort(int a[], int length)
{
??? bool swapFlag;
??? for (int i = 1; i < length; i++)? //兩個(gè)數(shù)，冒泡排序1次；length個(gè)數(shù)，冒泡排序length-1次。
??? {
??????? swapFlag = false;
??????? for (int j = 0; j < length - i; j++) //注意終止條件length-i，每次下沉一個(gè)最大數(shù)，不用比較到最后已確定的數(shù)。
??????? {
??????????? if (a[j] > a[j+1])
??????????? {
??????????????? swapFlag = true;
??????????????? swap(a[j], a[j+1]);
??????????? }
??????? }
?
??????? if (swapFlag == false)
??????? {
??????????? break;
??????? }
??? }
}
?
int?main() {
??? int array[9] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
?
??? bubbleSort(array,9);
?
??? for (int i = 0; i < 9; i++)
??? {
??????? cout << array[i] << endl;
??? }
??? return 0;
}

插入排序

將數(shù)插入到已排序數(shù)組中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include?<iostream>
#include?<vector>
using?namespace std;
?
template <class?T>
void?insertSort(vector<T> &vec)
{
?
??? for (int i = 1; i < vec.size(); i++)
??? {
??????? int j;
??????? T tmp = vec[i];
?
??????? for (j = i; (j > 0) && (tmp < vec[j-1]); j—) //是后移，不是交換。
??????? {
??????????? vec[j]=vec[j-1];
??????? }
?
??????? vec[j] = tmp;
??? }
}
?
int?main()
{
??? int array[9] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
??? vector<int> intVec(array, array + 9);
??? insertSort(intVec);
?
??? for (vector<int>::iterator iter = intVec.begin(); iter != intVec.end(); iter++) {
??????? cout << *iter << endl;
??? }
}

希爾排序

縮減增量排序，特殊的插入排序，每個(gè)增量的排序都是插入排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include?<iostream>
#include?<vector>
using?namespace std;
?
void?shellSort(vector<int> &a, int length)
{
??? for (int gap = length / 2; gap > 0; gap /= 2)
??? {
??????? for (int i = gap; i < length; i++)
??????? {
??????????? int j;
??????????? int tmp = a[i];
?
??????????? for (j = i; (j - gap >= 0) && (tmp < a[j-gap]); j -= gap)
??????????? {
??????????????? a[j] = a[j-gap];
??????????? }
??????????? a[j] = tmp;
??????? }
??? }
}
?
?
int?main() {
??? int a[] = {9,8,7,6,5,4,3,2,1,0,11};
??? vector<int> vec(a, a+11);
??? shellSort(vec, 11);
?
?
??? for (vector<int>::iterator iter = vec.begin(); iter != vec.end(); iter++) {
??????? cout << *iter << endl;
??? }
?
??? return 0;
}

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include?<iostream>
#include?<vector>
using?namespace std;
?
void?quicksort(vector<int> &v, int left, int right)
{
??? if (left >= right)
??? {
??????? return;
??? }
?
??? int low = left;
??? int high = right;??? //right是結(jié)束位，right-1是倒數(shù)第一個(gè)數(shù)。
??? int pivot = v[low];? //第一個(gè)值作為中樞值。
?
??? while (low < high)
??? {
??????? while (low < high && v[--high] > pivot)//--high從倒數(shù)第一個(gè)數(shù)向前找到第一個(gè)不大于key的值。
??????????? NULL;
??????? while (low < high && v[++low] < pivot)//從第2個(gè)數(shù)（v[low+1]）向后找到第一個(gè)不小于key的值(v[low]是中樞值，不參與排序).
??????????? NULL;
?
??????? if (low < high)
??????? {
??????????? swap(v[low], v[high]);
??????? }
??????? else
??????? {
??????????? break;
??????? }
??? }
?
??? swap(v[low], v[left]); //將中樞值與不大于中樞值的最大值交換，至此，v[low]是本次排序中樞值，low左邊的數(shù)都不大于中樞值，low右邊的數(shù)都不小于中樞值。
??? quicksort(v, left, low);
??? quicksort(v, low + 1, right);
}
?
int?main()
{
??? int a[10] =???? { 9,8,7,9,5,4,3,2,1,0 };
?
??? vector<int> vec(a, a + 10);
??? quicksort(vec, 0, 10);
??? for (vector<int>::iterator iter = vec.begin(); iter != vec.end();iter++)
??? {
??????? cout << *iter << endl;
??? }
?
??? return 0;
}