【C++】八大排序算法 ：GIF + 亲测代码 +专项练习平台

- 1、八大排序总览
- 代码实现一律放到文末，方便有兴趣边看边练的小伙伴动手自己写。
- 2、冒泡排序
- 3、快速排序
- 4、插入排序
- 5、希尔排序
- 6、选择排序
- 7、堆排序
- 8、归并排序
- 9、基数排序
- 各算法复杂度
    - 冒泡排序代码实现
    - 快速排序代码实现
    - 插入排序代码实现
    - 希尔排序代码实现
    - 选择排序代码实现
    - 归并排序
    - 基数排序
- 练习平台

#include<vector>
#include<iostream>

using namespace std;

void bulu(vector<int>& vec) {
	int sz = vec.size();
	if (sz == 0)
		return;
	int temp = 0;
	int continue_flag = 1;

	while (continue_flag) {
		for (int i = 0, j = 1; j < sz; i++, j++) {

			continue_flag = 0;

			if (vec[i] > vec[j]) {
				temp = vec[i];
				vec[i] = vec[j];
				vec[j] = temp;
				continue_flag = 1;
			}
		}
	}
}

int main()
{
	vector<int> test = { 2,5,1,5,3,7,5,7,5,6 };
	bulu(test);
	for (int i = 0; i < 10; i++) {
		cout << test[i] << " ";
	}
	return 0;
}

#include<iostream>
#include<cstdlib>

using namespace std;

//交换数组元素位置位置
void swap(int& a, int& b)
{
	int temp = a;
	a = b;
	b = temp;
}

/*
插入排序。注意，若后面一个元素比其前面一个元素小，则将这两个元素交换位置，然后再来比较这个插入元素与前面一个元素的大小，若小，则还需要交换这两个元素位置，一直到这个插入元素在正确的位置为止
*/
void insertSort(int a[], int length)
{
	for (int i = 1; i < length; i++)
	{
		for (int j = i - 1; j >= 0 && a[j + 1] < a[j]; j--)
		{
			swap(a[j], a[j + 1]);
		}
	}

}

int main()
{
	int a[] = { 2,1,4,5,3,8,7,9,0,6 };

	insertSort(a, 10);

	for (int i = 0; i < 10; i++)
	{
		cout << a[i] << " ";

	}
	cout << endl;
	system("pause");
	return 0;

}

int shellSort(int* shell,int ishell)
{
	int step,i,temp;
	step = ishell/3+1;	//	设定步长
	for( ; step>0 ;)
	{
		for(i=0 ; i+step<ishell ; )
		{
			if(shell[i] > shell[i+step])
			{
				temp = shell[i];
				shell[i] = shell[i+step];
				shell[i+step] = temp;
			}
			i++;
		}
		step--;
	}
}

void SelectSort(int* select,int lenth)
{
	int i,j,temp,min;
	for(i = 0;i<lenth;i++)
	{
		min = i;
		for(j = i+1;j<lenth;j++)
		{
			if(select[i]>select[j])
			{
				min = j;
			}
		}
		if(min != i)
		{
			temp = select[i];
			select[i] = select[min];
			select[min] = temp;
		}
	}
}

#include<iostream>
using namespace std;

void merge(int arr[], int L, int R, int M)
{
	int LEFT_SIZE = M - L;
	int  RIGHT_SIZE = R - M + 1;

	int* L_arr = new int [LEFT_SIZE];
	int* R_arr = new int[RIGHT_SIZE];

	
	int i,j,k;
	//将左边数组的值赋值给新数组
	for (i = L; i < M; i++)
	{
		L_arr[i - L] = arr[i];
	}
	
	//将右边数组的值赋值给新数组
	for (i = M; i <= R; i++)
	{
		R_arr[i - M] = arr[i];
	}

	i = 0, j = 0, k = L;
	//左右数组同时比较
	while (i < LEFT_SIZE && j < RIGHT_SIZE)
	{
		if (L_arr[i] < R_arr[j])
		{
			arr[k] = L_arr[i];
			i++;
			k++;

		}
		else
		{
			arr[k] = R_arr[j];
			j++;
			k++;
		}
	}

	while (i < LEFT_SIZE)
	{
		arr[k] = L_arr[i];
		i++;
		k++;
	}
	while (j < RIGHT_SIZE)
	{
		arr[k] = R_arr[j];
		j++;
		k++;
	}
}

void mergeSort(int arr[], int L, int R)
 {
	if (L == R)
	{
		return;
	}
	int M = (L + R) / 2;
	mergeSort(arr, L, M);
	mergeSort(arr, M+1, R);
	merge(arr, L,R,M+1);

}

int main()
{
	int arr[] = { 2,8,23,10,4,1,6,7 };
	int L = 0;
	int R = 7;
	int M = 4;
	//merge(arr, L, R, M);
	mergeSort(arr, L, R);

	for (int i = 0; i <= R; i++)
	{
		cout << arr[i] << endl;
	}

	return 0;
}

/*算法：基数排序*/
 
#include <iostream>
using namespace std;

bool rxsort(int A[],int l,int h,int d,int k){
    if(NULL==A||l>h)
        return false;
    int size = h-l+1;
 
    int* counts = new int[k];//用于计数排序的辅助数据，详见计数排序
    int* temp = new int[size];//用于存储重新排序的数组
    int index;
    int pval=1;
    //依次处理不同的位
    for(int i=0;i<d;i++){
        //counts数组清零
        for(int j=0;j<k;j++)
            counts[j] = 0;
 
        for(int j=l;j<=h;j++){
            /*
            1.data[j]/pval：去掉数字data[j]的后i个数，例如：
            当data[j]=1234,i=2时，此时pval=100,data[j]/pval=12;
            2.(data[j]/pval)%k：取数字data[j]/pval的最后一位数
            3.(int)(data[j]/pval)%k:取数字data[j]的第i位数
            */
            index = (int)(A[j]/pval)%k;
            /*
            统计数组A中每个数字的第i位数中各个数字的频数,用于计数排序；
            */
            counts[index]++;
        }
        //计算累加频数，用户计数排序
        for(int j=1;j<k;j++)
            counts[j] = counts[j] + counts[j-1];
        //使用倒数第i+1位数对A进行排序
        for(int j=h;j>=l;j--){
            index = (int)(A[j]/pval)%k;
            temp[counts[index]-1] = A[j];
            counts[index]--;
        }
        //将按第i为数排序后的结果保存回数组A中
        for(int j=0;j<size;j++)
            A[j+l] = temp[j];
        //更新pval
        pval = pval*k;
    }
    delete[] counts;
    delete[] temp;
}
 
int main(){
    int A[] = {712,303,4,18,89,999,70,26};
    rxsort(A,0,7,3,10);
    for(int i=0;i<8;i++)
        cout<<A[i]<<" ";
}