选择排序，插入排序，插入排序(移位)，冒泡排序，希尔排序（移位）的C++实现

选择排序，插入排序，插入排序(移位)，冒泡排序，希尔排序（移位）的C++实现及性能测试

选择排序：

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
/*
 * SelectionSort.h
 *
 *  Created on: 2018年5月5日
 *      Author: Will
 */

#ifndef BASIC_SORT_INSERTION_SORT_SELECTIONSORT_H_
#define BASIC_SORT_INSERTION_SORT_SELECTIONSORT_H_



template <typename T>
void selectionSort(T arr[],int n){
	for (int i = 0; i < n; ++i) {
		int minIndex = i;
		for (int j = i+1; j < n; ++j) {
			if(arr[j]<arr[minIndex]){
				minIndex = j;
			}
		}
		swap(arr[i],arr[minIndex]);
	}

	return;
}


#endif /* BASIC_SORT_INSERTION_SORT_SELECTIONSORT_H_ */

插入排序

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
	/*
 * InsertionSort.h
 *
 *  Created on: 2018年5月6日
 *      Author: Will
 */

#ifndef BASIC_SORT_INSERTION_SORT_INSERTIONSORT_H_
#define BASIC_SORT_INSERTION_SORT_INSERTIONSORT_H_



template<typename T>
void insertionSort(T arr[], int n) {
	for (int i = 1; i < n; ++i) {
//		for(int j = i ; j>0 ; --j){
//			if(arr[j]<arr[j-1]){
//				swap(arr[j-1],arr[j]);
//			}else{
//				break;
//			}
//		}

// 写法2
//        for( int j = i ; j > 0 && arr[j] < arr[j-1] ; j -- ){
//
//            swap( arr[j] , arr[j-1] );
//	}

//		// 写法3
		T temp = arr[i];
		int index;
//		       for(index = i ; index>0 && arr[index-1] > temp;--index){
//		    	   arr[index] = arr[index-1];
//		       }
//
//
//		       arr[index] = temp;

		for (index = i; index > 0; --index) {
			if (arr[index - 1] > temp) {
				arr[index] = arr[index - 1];
			} else {
				break;
			}
		}
		arr[index] = temp;
	}

	return;
}


#endif /* BASIC_SORT_INSERTION_SORT_INSERTIONSORT_H_ */

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
 * BubbleSort.h
 *
 *  Created on: 2018年5月6日
 *      Author: Will
 */

#ifndef BASIC_SORT_INSERTION_SORT_BUBBLESORT_H_
#define BASIC_SORT_INSERTION_SORT_BUBBLESORT_H_

template<typename T>
void bubbleSort(T arr[], int n) {
	for (int i = 0; i < n - 1; ++i) {

		for (int j = 0; j < n - i - 1; ++j) {
			if (arr[j] > arr[j + 1]) {
				swap(arr[j], arr[j + 1]);
			}
		}
	}
}

#endif /* BASIC_SORT_INSERTION_SORT_BUBBLESORT_H_ */

希尔排序-移位

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
/*
 * ShellSort.h
 *
 *  Created on: 2018年5月6日
 *      Author: Will
 */

#ifndef BASIC_SORT_INSERTION_SORT_SHELLSORT_H_
#define BASIC_SORT_INSERTION_SORT_SHELLSORT_H_

template<typename T>
void shellSort(T arr[], int n){

    // 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093...
	//取其序列的最大值，作为希尔排序的步进起始值
    int h = 1;
    while( h < n/3 )
    {
        h = 3 * h + 1;
    }

    while( h >= 1 ){

    	cout<<"希尔排序步进序列循环的值："<<h<<endl;
        // h-sort the array
        for( int i = h ; i < n ; i ++ ){

            T e = arr[i];
            // 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序
            int j;
            for( j = i ; j >= h && e < arr[j-h] ; j =j- h ){
                arr[j] = arr[j-h];
            }
            arr[j] = e;
        }

        h = h/3;
    }
}



#endif /* BASIC_SORT_INSERTION_SORT_SHELLSORT_H_ */

排序工具class.h

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
/*
 * SortUtils.h
 *
 *  Created on: 2018年5月5日
 *      Author: Will
 */

#ifndef BASIC_SORT_INSERTION_SORT_SORTUTILS_H_
#define BASIC_SORT_INSERTION_SORT_SORTUTILS_H_

#include <iostream>
#include <ctime>
#include <random>
#include <string>
#include <cassert>


using namespace std;

namespace SortUtils{
	int *arrayGenerator(int n,int left,int right){

//		assert(true);

		random_device rd;
		int *arr = new int[n];
		for(int i=0;i<n;++i){
			arr[i] = rd()%(right-left+1)+left;
		}

		return arr;
	}

	int *nearlyOrderArrayGenrator(int n,int swapTimes){
		random_device rd;
		int *arr = new int[n];
		for(int i=0;i<n;i++){
			arr[i] = i;
		}

		for(int i=0;i<swapTimes;++i){
			int posX = rd()%n;
			int posY = rd()%n;

			swap(arr[posX],arr[posY]);
		}

		return arr;

	}

	// 拷贝整型数组a中的所有元素到一个新的数组, 并返回新的数组
	    int *copyIntArray(int a[], int n){

	        int *arr = new int[n];
	        //* 在VS中, copy函数被认为是不安全的, 请大家手动写一遍for循环:)
	        copy(a, a+n, arr);
	        return arr;
	    }

    template <typename T>
    void printArray(T arr[],int n){
    	for(int i=0;i<n;++i){
    		cout<<arr[i]<<" ";
    	}
    	cout<<endl;
    }


    template<typename T>
    bool isSort(T arr[],int n){
//    	    	printArray(arr,n);
    	for(int i=0;i<n-1;++i){
    		if(arr[i]>arr[i+1]){
    			return false;
    		}
    	}

    	return true;
    }

    template<typename T>
    void testSort(string sortMethodName,void sortFunc(T[],int),T arr[],int n){
    	clock_t start = clock();
    	sortFunc(arr,n);
    	clock_t end = clock();

    	cout<<sortMethodName<<"==>"<<double(end-start)/CLOCKS_PER_SEC<<" second"<<endl;

    	assert(isSort(arr,n));

    	return;
    }
}

























#endif /* BASIC_SORT_INSERTION_SORT_SORTUTILS_H_ */

测试-主函数

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
/*
 * InsertionSort.cpp
 *
 *  Created on: 2018��5��5��
 *      Author: Will
 */

#include <iostream>
#include "SortUtils.h"
#include "SelectionSort.h"
#include "BubbleSort.h"
#include "InsertionSort.h"
#include "ShellSort.h"

using namespace std;





int main() {
	int n = 20000;
	cout << "随机数组长度为==》" << n << endl;
	int *arr1 = SortUtils::arrayGenerator(n, 0, n);
	int *arr2 = SortUtils::copyIntArray(arr1, n);
	int *arrBubble1 = SortUtils::copyIntArray(arr1, n);
	int *arrShell1 = SortUtils::copyIntArray(arr1, n);

//	SortUtils::printArray(arr1,n);
//	SortUtils::printArray(arr2,n);

	int *arr3 = SortUtils::arrayGenerator(n, 0, 5);
	int *arr4 = SortUtils::copyIntArray(arr3, n);
	int *arrBubble2 = SortUtils::copyIntArray(arr3, n);
	int *arrShell2 = SortUtils::copyIntArray(arr3, n);

	int swapTimes = 100;
	int *arr5 = SortUtils::nearlyOrderArrayGenrator(n, swapTimes);
	int *arr6 = SortUtils::copyIntArray(arr5, n);
	int *arrBubble3 = SortUtils::copyIntArray(arr5, n);
	int *arrShell3 = SortUtils::copyIntArray(arr5, n);

	SortUtils::testSort("random-选择排序", selectionSort, arr1, n);
	SortUtils::testSort("random-插入排序", insertionSort, arr2, n);
	SortUtils::testSort("random-冒泡排序",bubbleSort,arrBubble1,n);
	SortUtils::testSort("random-Shell排序",shellSort,arrShell1,n);

	cout<<endl;

	SortUtils::testSort("more order 选择排序", selectionSort, arr3, n);
	SortUtils::testSort("more order 插入排序", insertionSort, arr4, n);
	SortUtils::testSort("more order 冒泡排序", bubbleSort, arrBubble2, n);
	SortUtils::testSort("more order Shell排序", shellSort, arrShell2, n);

	cout<<endl;

	SortUtils::testSort("nearly order 选择排序", selectionSort, arr5, n);
	SortUtils::testSort("nearly order 插入排序", insertionSort, arr6, n);
	SortUtils::testSort("nearly order 冒泡排序", bubbleSort, arrBubble3, n);
	SortUtils::testSort("nearly order Shell排序", shellSort, arrShell3, n);

//	SortUtils::printArray(arr1,n);
//	SortUtils::printArray(arr2,n);
	delete[] arr1;
	delete[] arr2;
	delete[] arr3;
	delete[] arr4;
	delete[] arr5;
	delete[] arr6;
	delete[] arrShell1;
	delete[] arrShell2;
	delete[] arrShell3;
	delete[] arrBubble1;
	delete[] arrBubble2;
	delete[] arrBubble3;
//
	cout << 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
随机数组长度为==》20000
random-选择排序==>1.098 second
random-插入排序==>0.566 second
random-冒泡排序==>3.749 second
希尔排序步进序列循环的值：9841
希尔排序步进序列循环的值：3280
希尔排序步进序列循环的值：1093
希尔排序步进序列循环的值：364
希尔排序步进序列循环的值：121
希尔排序步进序列循环的值：40
希尔排序步进序列循环的值：13
希尔排序步进序列循环的值：4
希尔排序步进序列循环的值：1
random-Shell排序==>0.005 second

more order 选择排序==>1.227 second
more order 插入排序==>0.514 second
more order 冒泡排序==>2.727 second
希尔排序步进序列循环的值：9841
希尔排序步进序列循环的值：3280
希尔排序步进序列循环的值：1093
希尔排序步进序列循环的值：364
希尔排序步进序列循环的值：121
希尔排序步进序列循环的值：40
希尔排序步进序列循环的值：13
希尔排序步进序列循环的值：4
希尔排序步进序列循环的值：1
more order Shell排序==>0.002 second

nearly order 选择排序==>0.759 second
nearly order 插入排序==>0.006 second
nearly order 冒泡排序==>0.925 second
希尔排序步进序列循环的值：9841
希尔排序步进序列循环的值：3280
希尔排序步进序列循环的值：1093
希尔排序步进序列循环的值：364
希尔排序步进序列循环的值：121
希尔排序步进序列循环的值：40
希尔排序步进序列循环的值：13
希尔排序步进序列循环的值：4
希尔排序步进序列循环的值：1
nearly order Shell排序==>0.003 second

总结：

选择排序：取得外循环的被选择的元素的下标，然后将该元素与右侧所有元素依次比较大小，如右侧元素小于取得下标的元素，则将下表赋值为较小元素的下标，直至到数列最后一个元素停止内层循环，

特点：

1.外循环被选中的元素的左侧的元素总是排好序的而且是最终所在的位置。

2.换位操作在外循环中实现，比插入排序在内层循环中换位性能要好。

3.对乱序，中度有序，接近有序的排序的耗时稳定在O($N^2$)级别

插入排序：取得外层循环中的元素，将其与其左侧元素做比较，如果左侧元素较大，则将当前元素与左侧元素换位。

特点：

1.当前元素的左侧元素总是有序的，因此，如果当前元素比其左侧元素大时，可以直接终止内层循环。这使得插入排序对接近有序的数列的排序耗时接近O(N)，也就是说插入排序在特定的，有序性较强的数列排序时比选择排序耗时更短。

2.换位操作发生在内层循环，换位耗时较长，因此衍生出改进型的插入排序：插入排序-移位

插入排序-移位：选择在内存里保存一份外层循环(外循环下标从1开始，即从第二个元素开始)的需要插入的元素（记为C）的副本（记为T），然后将该元素的副本T逐次地与其左侧元素做比较，如果左侧元素较大，则将左侧元素（记为L）与L右侧的元素移位（即L的位置空出，L+1的位置赋值成L，因为C的值已被复制成副本T，所以C的位置可以被其左侧的元素的值覆盖），直至没有元素比T大时，将空置的位置下标的元素赋值成T。

特点：

1.内层循环中由换位操作（开辟新内存，三次赋值操作）改良为赋值操作（移位操作），外层每次循环也仅有一次赋值操作。与选择排序相比，既保留了对接近有序数列排列耗时的优势，又在对无序数列排序时获得较好的性能优势。

2.仍然存在数列中的较小的值在数列右侧远端，需要逐次移位其左侧所有元素的操作。而希尔排序则为解决此类问题作出进一步的优化。

希尔排序：采用特定的数列作为步进数列，将待排序数列（记为arr）按照步进数列的每次取得的值（记为n）做切分。必须注意到，数列总能将下标按照n的步进切分成n个数列。于是，可以将arr按照被切分的数列，按照每次步进n进行插入排序（可以选用插入排序-移位做进一步的优化）。对同一步进的所有数列做插入排序，意味着，在程序上，就是从步进n开始到arr最右侧元素终止，做步进是n的插入排序操作。

特点：

1.采用步进数列，解决了arr数列右侧远端是较小值的逐次比较的问题，改良为按照步进大小进行n位移的大跨步的调整。

2.如果采用3n+1的步进数列，在arr数量级较小的情况下，相对归并，快速排序，代码实现起来较为简单，但能获得相近的性能。

赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家