排序算法 | 我的日常分享

排序算法

发表于2020-09-23更新于2020-09-23字数统计2k阅读时长24分

排序算法

一、直接插入排序

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
//进行从小到大排序
void insertSmallToLarge(int *arr,int m,int temp){
	int i = 0;
	for(i=m-1;i>=0;i--){
		if(temp < *(arr+i)){
			*(arr+i+1) = *(arr+i);
		}else{
			break;
		}
	}
	*(arr+i+1)=temp;
}
//从大到小进行排序
void insertLargeToSmall(int *arr,int m,int temp){
	int i = 0;
	for(i=m-1;i>=0;i--){
		if(temp > *(arr+i)){
			*(arr+i+1) = *(arr+i);
		}else{
			break;
		}
	}
	*(arr+i+1)=temp;
}
//配合上面的两个函数使用
void insertSort(int *arr,int n){
	
	for(int i = 1; i < n; i++){
		insertSmallToLarge(arr,i,*(arr+i)); 
		insertLargeToSmall(arr,i,*(arr+i));
	}
	
}

直接插入法程序：

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
#include<ctime>
#include<cstdlib>
using namespace std;
void insertSmallToLarge(int* arr, int m, int temp);
void insertLargeToSmall(int* arr, int m, int temp);
void insertSort(int* arr, int n);
void output(int* arr, int n);
void inputRandCount(int *arr, int n);
void dynamicApplication(int*& arr, int &n);
int main()
{
    int n = 0,*arr=NULL;
    //动态申请内存
    dynamicApplication(arr, n);
    //输入随机数
    inputRandCount(arr, n);
    //输出原先的数组
    cout << "原先的数组为：" << endl;
    output(arr, n);
    //进行插入排序
    insertSort(arr, n);
    //输出排序好的数组
    cout << "排序后的数组为："<<endl;
    output(arr, n);
    //释放内存
    free(arr);
}
//将temp插入有序数组a[1..n-1]中，数组a仍然有序
void Insert(int* a, int n, int temp)
{
    int i = 0;
    for (i = n - 1; i >= 0; i--) //查找插入位置
    {
        if (temp < a[i])  //  后移
            a[i + 1] = a[i];
        else
            break;
    }
   a[i + 1] = temp;  //  插入数据到正确位置
}


//进行从小到大排序
void insertSmallToLarge(int* arr, int m, int temp) {
    int i = 0;
    for (i = m - 1; i >= 0; i--) {
        if (temp < *(arr + i)) {
            *(arr + i + 1) = *(arr + i);
        }
        else {
            break;
        }
    }
    *(arr + i + 1) = temp;
}
//从大到小进行排序
void insertLargeToSmall(int* arr, int m, int temp) {
    int i = 0;
    for (i = m - 1; i >= 0; i--) {
        if (temp > * (arr + i)) {
            *(arr + i + 1) = *(arr + i);
        }
        else {
            break;
        }
    }
    *(arr + i + 1) = temp;
}
//配合上面的两个函数使用 对数组arr作直接插入排序
void insertSort(int* arr, int n) {

    for (int i = 1; i < n; i++) {
        insertSmallToLarge(arr, i, *(arr + i));
        //insertLargeToSmall(arr, i, *(arr + i));
    }

}
//输出数组arr的元素
void output(int* arr,int n) {
    for (int i = 0; i < n; i++) {
        cout << *(arr + i) << " ";
    }
    cout << endl;
}
//生成随机数
void inputRandCount(int *arr, int n) {

    srand((unsigned)time(NULL));
    for (int i = 0; i < n; i++)
    {
        *(arr + i) = rand() % 1000;
    }
}
//动态申请内存空间
void dynamicApplication(int*& arr, int &n) {
    cout << "请输入数组的元素个数n：" << endl;
    cin >> n;
    //动态申请内存空间
    arr = (int*)malloc(sizeof(int) * n);
    //判断内存是否申请成功
    if (NULL == arr) {
        perror("malloc");
        exit(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
//比较数组相邻的两个元素进行交换 使最后一个元素值最大 
void compToMax(int *arr,int n){
	for(int i=0;i<n-1;i++){
		if(arr[i]>arr[i+1]){
			swap(arr[i],arr[i+1]);
		}
	}
}
//比较数组相邻的两个元素进行交换 使最后一个元素值最小 
void compToMin(int *arr,int n){
	for(int i = 0; i < n-1; i++){
		if(arr[i]<arr[i+1]){
			swap(arr[i],arr[i+1]);
		}
	} 
}
//进行起泡排序
void bubbleSort(int *arr,int length){
	for(int i = length; i>1;i--){
		compToMax(arr,i);
	} 
}
//交换a b的值
void swap(int &a,int &b){
	int temp=0;
	temp = a;
	a = b;
	b = temp;
}

起泡排序法程序：

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include<ctime>
#include<cstdlib>
using namespace std;
void compToMax(int* arr, int n);
void compToMin(int* arr, int n);
void bubbleSort(int* arr, int length);
void swap(int& a, int& b);
void output(int* arr, int n);
void inputRandCount(int *arr, int n);
void dynamicApplication(int*& arr, int &n);
int main(int argc,char *argv[])
{
    int n = 0,*arr=NULL;
    //动态申请内存
    dynamicApplication(arr, n);
    //输入随机数
    inputRandCount(arr, n);
    //输出原先的数组
    cout << "原先的数组为：" << endl;
    output(arr, n);
    //进行插入排序
    bubbleSort(arr, n);
    //输出排序好的数组
    cout << "排序后的数组为："<<endl;
    output(arr, n);
    //释放内存
    free(arr);
}

//比较数组相邻的两个元素进行交换 使最后一个元素值最大 
void compToMax(int* arr, int n) {
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            swap(arr[i], arr[i + 1]);
        }
    }
}
//比较数组相邻的两个元素进行交换 使最后一个元素值最小 
void compToMin(int* arr, int n) {
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] < arr[i + 1]) {
            swap(arr[i], arr[i + 1]);
        }
    }
}
//进行起泡排序
void bubbleSort(int* arr, int length) {
    for (int i = length; i > 1; i--) {
        compToMax(arr, i);
        //compToMin(arr, i);
    }
}
//交换a b的值
void swap(int& a, int& b) {
    int temp = 0;
    temp = a;
    a = b;
    b = temp;
}
//输出数组arr的元素
void output(int* arr,int n) {
    for (int i = 0; i < n; i++) {
        cout << *(arr + i) << " ";
    }
    cout << endl;
}
//生成随机数
void inputRandCount(int *arr, int n) {

    srand((unsigned)time(NULL));
    for (int i = 0; i < n; i++)
    {
        *(arr + i) = rand() % 1000;
    }
}
//动态申请内存空间
void dynamicApplication(int*& arr, int &n) {
    cout << "请输入数组的元素个数n：" << endl;
    cin >> n;
    //动态申请内存空间
    arr = (int*)malloc(sizeof(int) * n);
    //判断内存是否申请成功
    if (NULL == arr) {
        perror("malloc");
        exit(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
//找到比arr[m]更小的数 并返回其下标 
int selectMinKey(int* arr, int m, int length) {
    int min = m;
    for (int i = m + 1; i < length; i++) {
        if (arr[i] < arr[min]) {
            min = i;
        }
    }
    return min;
}
//找到比arr[m]更大的数 并返回其下标 
int selectMaxKey(int* arr, int m, int length) {
    int max = m;
    for (int i = m + 1; i < length; i++) {
        if (arr[i] > arr[max]) {
            max = i;
        }
    }
    return max;
}
//进行直接选择排序  从小到大排序 
void selectSortToMin(int* arr, int length) {
    int min = 0;
    for (int i = 0; i < length; i++) {
        min = selectMinKey(arr, i, length);
        swap(arr[i], arr[min]);
    }
}
//进行直接选择排序  从大到小排序 
void selectSortToMax(int* arr, int length) {
    int max = 0;
    for (int i = 0; i < length; i++) {
        max = selectMaxKey(arr, i, length);
        swap(arr[i], arr[max]);
    }
}
//交换a b的值
void swap(int& a, int& b) {
    int temp = 0;
    temp = a;
    a = b;
    b = temp;
}

直接选择排序程序

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <iostream>
#include<ctime>
#include<cstdlib>
using namespace std;
int selectMinKey(int* arr, int m, int length);
void selectSortToMin(int* arr, int length);
void selectSortToMax(int* arr, int length);
void swap(int& a, int& b);
void output(int* arr, int n);
void inputRandCount(int *arr, int n);
void dynamicApplication(int*& arr, int &n);
int main(int argc,char *argv[])
{
    int n = 0,*arr=NULL;
    //动态申请内存
    dynamicApplication(arr, n);
    //输入随机数
    inputRandCount(arr, n);
    //输出原先的数组
    cout << "原先的数组为：" << endl;
    output(arr, n);
    //进行选择排序 从小到大
    selectSortToMin(arr, n);
    //输出排序好的数组
    cout << "排序后的数组为："<<endl;
    output(arr, n);
    //释放内存
    free(arr);
}
//找到比arr[m]更小的数 并返回其下标 
int selectMinKey(int* arr, int m, int length) {
    int min = m;
    for (int i = m + 1; i < length; i++) {
        if (arr[i] < arr[min]) {
            min = i;
        }
    }
    return min;
}
//找到比arr[m]更大的数 并返回其下标 
int selectMaxKey(int* arr, int m, int length) {
    int max = m;
    for (int i = m + 1; i < length; i++) {
        if (arr[i] > arr[max]) {
            max = i;
        }
    }
    return max;
}
//进行直接选择排序  从小到大排序 
void selectSortToMin(int* arr, int length) {
    int min = 0;
    for (int i = 0; i < length; i++) {
        min = selectMinKey(arr, i, length);
        swap(arr[i], arr[min]);
    }
}
//进行直接选择排序  从大到小排序 
void selectSortToMax(int* arr, int length) {
    int max = 0;
    for (int i = 0; i < length; i++) {
        max = selectMaxKey(arr, i, length);
        swap(arr[i], arr[max]);
    }
}
//交换a b的值
void swap(int& a, int& b) {
    int temp = 0;
    temp = a;
    a = b;
    b = temp;
}
//输出数组arr的元素
void output(int* arr,int n) {
    for (int i = 0; i < n; i++) {
        cout << *(arr + i) << " ";
    }
    cout << endl;
}
//生成随机数
void inputRandCount(int *arr, int n) {

    srand((unsigned)time(NULL));
    for (int i = 0; i < n; i++)
    {
        *(arr + i) = rand() % 1000;
    }
}
//动态申请内存空间
void dynamicApplication(int*& arr, int &n) {
    cout << "请输入数组的元素个数n：" << endl;
    cin >> n;
    //动态申请内存空间
    arr = (int*)malloc(sizeof(int) * n);
    //判断内存是否申请成功
    if (NULL == arr) {
        perror("malloc");
        exit(0);
    }
}