7个常见的排序算法

7个常见的排序算法

1.冒泡排序   2.选择排序

3.插入排序   4.希尔排序

5.计数排序

6.归并排序   7.快速排序

Notice：数组大小为n，除计排外数组均定义为a[]，下标为1~n，排序默认均为升序，时间复杂度为平均复杂度

1.冒泡排序

时间复杂度：O(N^2)

（两两元素进行比较，较小的数向前浮动）

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

2.选择排序

时间复杂度：O(N^2)

（不断执行 *** 作：选出未经排序的一系列数的最小值，放到数组最前面）

void Select_sort(int a[], int n)
{
    int minx,minn;
    for(int i=1;i < n;i++){
        //minn存放每一趟排序中的最小数，minx存放下标
        minn=a[i];  minx=i;
        for(int j=i+1;j<=n;j++){
                if(minn > a[j]) minn = a[j],minx=j;
        }
        if(minx != i)
        swap(a[i],a[minx]);
    }
}

3.插入排序

时间复杂度：O(N^2)

（拿出第一个乱序数，放到已经排好序的序列的合适位置）

void insert_sort(int a[],int n)
{
    int i,j,temp;
	for(i = 2; i <= n; i++)
	{
        //取出要插入的数
        temp = a[i];
		for(j = i; j > 1 && a[j - 1] > temp; j--)
			//寻找合适的插入位置
            a[j] = a[j - 1];
        //插入数值
		a[j] = temp;
	}
}

4.希尔排序（对半式增量）

时间复杂度：O(N^1.5)左右

（不断的进行 *** 作：在原数组中按照一定间隔mid从头到尾取出一系列数形成几个新的序列——>对每个新的序列进行排序——>序列合并）

对半式增量：

比如一个长度为8的数组，8/2 = 4，所以第一次就按间隔为4取数，那么形成的新序列的下标就是：<1 5>,<2 6>,<3 7>,<4 8>

第二次间隔为4/2 = 2，则新取出的序列为<1 3 5 7>,<2 4 6 8>

最后一次间隔就是2/2 = 1，直接进行插入排序搞定

void Shell_sort(int a[],int n)
{
	int j,i,temp,mid;    //增量定义为mid
	for(mid = n/2; mid > 0; mid /= 2){
        //一个插入排序的过程代码，只不过要注意间隔的存在
		for(i = mid; i <= n; i++){
			temp = a[i];
			for(j = i; j > mid; j -= mid) {
				if(a[j - mid] > temp)
					a[j] = a[j - mid];
				else  break;
			}
			a[j] = temp;
		}
	}
}

5.计数排序

时间复杂度：O(d(n+r))

(例如a[2] = 1，意思是2这个元素出现了1次）

(适用于数据集中，数据范围较小且比较明确的情况)

#include
using namespace std;
#define MAXN 10000
int cnt[MAXN+1],n,temp;;
int main(void)
{
    //输入
    memset(cnt,0,sizeof(cnt));
    cin >>n;
    for(int i = 1; i <= n; i++){
        cin >>temp;
        cnt[temp]++; //计数
    }
    //输出
    for(int i = 0; i <= MAXN; i++){
        if(cnt[i]){ //检测数字i有没有出现过
            //出现几次输出几个i
            for(int j = 1; j <= cnt[i]; j++) cout < 
 
6.归并排序（递归，分治）
 
时间复杂度：O(nlog2n)(2是底数)
 
 
//这里a和b数组没有声明，应该写到外面，a数组是录入数据的数组
void Merge_sort(int l, int r)
{
    //递归到了只有一个元素，直接返回
    if(l == r) return;
    //找到中点，然后两边分别再归并
    int mid = (l + r) / 2;
    Merge_sort(1, mid);
    Merge_sort(mid + 1, r);
    //合并序列
    int p = 1, q = mid + 1;
    for(int i = 1; i <= r; i++){
        if(q > r || (p <= mid && a[p] <= a[q])) b[i] = a[p++];
        else b[i] = a[q++];
    }
    //还原到a数组里
    for(int i = 1; i <= r; i++) a[i] = b[i];
}
 
7.快速排序
 
时间复杂度：O(nlog2n)(2是底数)
 
(找一个基准，然后将小于这个基准的数放到索引的左边，大于基准的数放到索引右边
 
不断执行这个 *** 作直到有序，这里基准取的是中间数)
 
//a数组未定义
void Quick_sort( int L, int R)
{
    int l = L, r = R;
    //定义基准点
    int mid = (L + R) / 2;
    int x = a[mid];
    while(l < r){
        //找到两边的逆序点
        while(a[l] < x && l < r) l++;
        while(a[r] > x && l < r) r--;
            //交换
            if(l < r){
            swap(a[l], a[r]);
            l++,r--;
        }
    }
    //左右两边继续快排
    if(L < r) Quick_sort(L, r);
    if(l > R) Quick_sort(l,R);
}
 
 
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://www.outofmemory.cn/zaji/5710536.html