首页 > 其他分享 >排序

排序

时间：2023-05-10 22:45:15浏览次数：30  
标签：arr int void len NUM 排序 left 

//冒泡排序
void bubble_sort(int* a, int len){
    //n-1次
    for (int i = 0; i < len - 1; i++){
        //比较相邻两个，大的后挪
        for (int j = 0; j < len - i - 1; j++){
            if (a[j] > a[j + 1]){//比较相邻两个  不满足要求
                //交换
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }

        //travel(a, len);
    }
}


//选择排序
void select_sort(int* a, int len)
{
    int temp;
    size_t minIdx;
    for (int i = 0; i < len - 1; i++)
    {//选 len -1 次
        temp = a[i];//备份 a[i] 位置 的数据
        minIdx = i;//假设 a[i]最小
        //找出   i 到 len-1  范围内最小数据 记录其下标
        for (int j = i; j < len; j++)
            minIdx = ((a[j] < a[minIdx]) ? j : minIdx);
        //最小的  放到  a[i] 位置
        if (a[minIdx] < temp)
        {
            a[i] = a[minIdx];
            a[minIdx] = temp;
        }

        //travel(a, len);
    }
}


 

//插入排序
void insert_sort(int* a, int len)
{
    int temp;
    int insertIdx;
    //插入次数 n-1 次 
    for (int i = 1; i < len; i++)
    {//每次把下标为i元素插入到已序数组中
        //临时存储 待插数据
        temp = a[i];
        //从 i-1位置开始往前找插入位置


        for (insertIdx = i - 1; insertIdx >= 0 && a[insertIdx] > temp; insertIdx--)
        {
            a[insertIdx + 1] = a[insertIdx];
        }

        //找到后  插入
        a[insertIdx + 1] = temp;
        //travel(a, len);
    }


}
#include <stdio.h>
/*
基数排序
    a:数组
    len:元素个数
    max：最大元素值
*/
void radix_sort(int* a,int len,int max);

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

    radix_sort(arr, 10,9);

    for (int i = 0; i < 10; i++)
        printf("%d ", arr[i]);
    printf("\n");

    while (1);
    return 0;
}

/*
基数排序
a:数组
len:元素个数
max：最大元素值
*/
void radix_sort(int* a, int len, int max){
    //定义一个临时数组
    int* pTemp = new int[max + 1];

    for (int i = 0; i < max + 1; i++)
        pTemp[i] = -1;

    //把a数组中元素依序存入pTemp数组中
    for (int i = 0; i < len; i++)
        pTemp[a[i]] = a[i];

    //把pTemp数组覆盖回来
    int k = 0;
    for (int i = 0; i < max + 1; i++){
        if (pTemp[i] != -1)
            a[k++] = pTemp[i];
    }
    //释放
    delete[] pTemp;
}
#include <iostream>
using namespace std;
//元素个数
#define NUM  10
//数据范围
#define AREA 1000
//箱子个数
#define SIZE  10

void init(int* a);
void travel(int* a, int len, bool isAfter=false);
//箱排序
void bucket_sort(int* a, int len);
int main(){
    int arr[NUM];
    init(arr);

    travel(arr,NUM);

    bucket_sort(arr, NUM);

    travel(arr, NUM,true);
    while (1);
}

//箱排序
void bucket_sort(int* a, int len){
    int count;//用来做循环次数的循环变量
    //做箱子
    int* pTemp = new int[SIZE * len];
    int k;
    /*
        int pTemp[SIZE][len];
        pTemp[a[i] /count%10][i]
    */
    for (count = 1; count < AREA; count *= 10){
        //1 初始化10个箱子
        for (int i = 0; i < SIZE * len; i++){
            pTemp[i] = -1;
        }
        //2 根据当前位把a数组中元素放到箱子里
        //  看对应十进制为    a[i] /count%10
        for (int i = 0; i < len; i++){
            //pTemp[a[i] /count%10][i]

            pTemp[(a[i] / count % 10)*len + i] = a[i];
        }

        //3 覆盖回来
        k = 0;
        for (int i = 0; i < SIZE * len; i++){
            if (-1 != pTemp[i]){
                a[k++] = pTemp[i];
            }
        }

        travel(a, NUM);
    }
    delete[] pTemp;
}


void init(int* a){
    for (int i = 0; i < NUM; i++)
        a[i] = rand() % AREA;
}
void travel(int* a, int len, bool isAfter){
    if (isAfter){
        cout << "after  sort:";
    }
    else{
        cout << "before sort:";
    }

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

    cout << endl;
}

 

/*
循环方式实现二分查找
从arr数组中找值为findData的元素
找到返回其下标 找不到返回-1
len为数组元素个数
*/
int halfFind(int* arr, int len, const int& findData){
    int m;                //中间的下标
    int left=0;            //左边下标
    int right=len-1;    //右边下标
    while (1){
        //把中间下标算出来
        m = left + (right - left) / 2;
        if (findData == arr[m]){//判断是否找到了  
            return m;//找到了 返回
        }
        else{
            //没找到  修改left和right的值  继续循环
            if (findData > arr[m]){//要找数据比中间数据大 
                left = m + 1;//排除掉左边
            }
            else{//要找数据比中间数据小 
                right = m - 1;//排除掉右边
            }
        }
        if (left > right) break;//找不到 防止死循环
    }
    return -1;
}

/*
递归方式实现二分查找
从arr数组中找值为findData的元素
找到返回其下标 找不到返回-1
len为数组元素个数
*/
int half_find(int* arr, int len, const int& findData){
    return Half_Find(arr, 0, len - 1, findData);
}
//用于递归的函数
int Half_Find(int* arr, int left, int right, const int& findData){
    if (left > right) 
        return -1;
    int m = left + (right - left) / 2;
    if (findData == arr[m])
    {//判断是否找到了  
        return m;//找到了 返回
    }
    //没找到  修改left和right的值  继续循环
    if (findData > arr[m])
    {//要找数据比中间数据大 
        return Half_Find(arr, m + 1, right, findData);
    }
    else
    {//要找数据比中间数据小 
        return Half_Find(arr, left, m - 1, findData);
    }
}
#include <iostream>
using namespace std;

#define NUM 18
void travel(int* a, int len, bool isAfter = false);

/*
    left  - mid   左边的
    mid+1 - right 右边的
*/
void MergeSort(int* a, int left, int mid, int right);

//归并排序
void merge_sort(int* a, int left, int right);
//常规写法归并排序
void mergeSort(int* a, int len);

int main(){
#if 1    
    int arr[NUM] = { 31, 41, 59, 26, 53, 58, 97, 93, 23, 84, 62, 64,
        33, 83, 27, 95, 2, 88 };
#else
    int arr[NUM] = {    23, 26, 31, 41, 53, 58, 59, 93, 97, 
        2, 27, 33, 62, 64, 83, 84, 88, 95 };
#endif
    
    travel(arr, NUM, true);

    //MergeSort(arr, 0, 0 + (NUM - 1 - 0) / 2, NUM - 1);
    //MergeSort(arr, 0, 8, 17);

    //merge_sort(arr, 0, 17);
    mergeSort(arr, NUM);
    travel(arr, NUM, true);

    

    while (1);
    return 0;
}

void travel(int* a, int len, bool isAfter){
    if (isAfter){
        cout << "after  sort:";
    }
    else{
        cout << "before sort:";
    }

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

    cout << endl;
}


/*
left  - mid   左边的
mid+1 - right 右边的
*/
void MergeSort(int* a, int left, int mid, int right){
    int L = left;
    int R = mid + 1;
    int k = 0;//作为pTemp的下标
    //1 申请临时内存空间
    int* pTemp = new int[right - left + 1];
    //2 一边比较一边把数据从a放到pTemp中
    while (L<=mid && R<=right){
        if (a[L] < a[R])    pTemp[k++] = a[L++];
        else                pTemp[k++] = a[R++];
    }
    //3 把剩下的一半放入pTemp中
#if 0
    while (L <= mid){ pTemp[k++] = a[L++]; }
    while (R <= right){ pTemp[k++] = a[R++]; }
#else
    
    if (L <= mid){
        memcpy(pTemp + k, a + L, sizeof(int)*(mid-L+1));
    }
    else{
        memcpy(pTemp + k, a + R, sizeof(int)*(right-R+1));
    }
#endif
    //4 pTemp中数据覆盖回 a
#if 0
    int j = 0;
    for (int i = left; i <= right; i++){
        a[i] = pTemp[j++];
    }
#else
    memcpy(a + left, pTemp, sizeof(int)*(right - left + 1));
#endif
    //5 释放
    delete[] pTemp;
}

//归并排序
void merge_sort(int* a, int left, int right){
    if (left < right){
        int m = left + (right - left) / 2;
        //拆
        merge_sort(a, left, m);        //左边
        merge_sort(a, m + 1, right);//右边
        //合
        MergeSort(a, left, m, right);
        //travel(a+left, right-left+1);
    }
}
//常规写法归并排序
void mergeSort(int* a, int len){
    merge_sort(a, 0, len - 1);
}
#include <iostream>
using namespace std;
#define NUM 18
void travel(int* a, int len, bool isAfter = false);

//分组排序
void quick_sort(int* a, int left, int right);

int main(){
    int arr[NUM] = { 31, 41, 59, 26, 53, 58, 97, 93, 23, 84, 62, 64,
        33, 83, 27, 95, 2, 88 };
    travel(arr, NUM, true);

    quick_sort(arr, 0, 17);

    travel(arr, NUM, true);
    while (1);
    return 0;
}
void travel(int* a, int len, bool isAfter){
    if (isAfter){
        cout << "after  sort:";
    }
    else{
        cout << "before sort:";
    }

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

    cout << endl;
}

//分组排序
void quick_sort(int* a, int left, int right){
    if (left >= right) return;

    //假设a[left]是中间数据
    int temp = a[left];
    int L = left;    //用来移动的左下标
    int R = right;  //用来移动的右下标

    //循环让L和R并拢
    while (L < R){
        //先挪R
        while (L<R && a[R] > temp) R--;
        a[L] = a[R];
        //再挪L
        while (L < R && a[L] < temp) L++;
        a[R] = a[L];
    }
    a[L] = temp;

    travel(a, NUM);

    //继续拆
    quick_sort(a, left, L - 1);//左边
    quick_sort(a, L+1, right);//右边
}

 

标签：arr,int,void,len,NUM,排序,left
From： https://www.cnblogs.com/yewu1/p/17386126.html

相关文章

  • 拓扑排序 - TopoSort
    拓扑排序-TopoSort前言wcy终于考上了心仪的大学，开启了精彩的大学生活！然而光是选课这一件事就把他难住了，因为一些课程包含先修课程：课程编号课程名称先修课程C1高等数学无C2程序设计基础无C3离散数学C1,C2C4数据结构C2,C3C5算法语言C2C6......
  • MySQL的随机排序（random orderby）
    MySQL的随机排序（randomorderby）是指在查询数据库时，将结果集以随机的方式排列。这种排序方式可以用于有趣的应用场景，例如实现随机音乐播放、广告推荐等。要实现MySQL的随机排序，可以使用RAND()函数。RAND()函数可以生成0-1之间的随机数，将它作为排序的依据即可。SELECT*FROM`my......
  • 冒泡排序
    importjava.util.Arrays;/***@Auther:么么*@Date:2023/5/8-05-08-22:16*@Description:PACKAGE_NAME*@version:1.0*///冒泡排序publicclasstest02{//这是一个main方法，是程序的入口：publicstaticvoidmain(String[]args){......
  • KingbaseES V8R6运维案例之---MySQL和KingbaseES字符串排序规则对比
    案例说明：相同数据排序后查询，在MySQL和KingbaseES下得到的排序顺序不一致，本案例从MySQL和KingbaseES的排序规则分析，两种数据库排序的异同点。适用版本：KingbaseESV8R6、MySQL8.0一、MySQL的排序规则1、排序规则（collation）排序规则是依赖于字符集，字符集是用来定义MySQL存储不......
  • 关于白话排序之快速排序以及维基百科的希尔排序
    1、白话排序的快速排序中，“坑”的形象概念，很好好好2、维基百科中，将每次的间隔的元素，不是采用白话中所用的A1、A2等的形式，而是采用直接放在一列，进行列排序的形象概念，很好好好3、希尔排序，最外边一层是gap的减少，里面两层---》插入排序。。。。。。......
  • vue sort 排序方法
    1、数据排序vararry=[9,5,6,7,5,6,3,1,0]arry.sort()//[0,1,3,5,5,6,6,7,9] 2、对象排序varlist=[{name:'张三'，age:12},{name:'李四','age:23}];list.sort((a,b)=>{returna.age-b.age});//[{name:'李四','ag......
  • 简单选择排序
    简单选择排序算法思想：遍历整个数组，每一趟找出最小的那个数，放在数组前面importjava.util.Arrays;/***@Auther:么么*@Date:2023/5/8-05-08-22:05*@Description:PACKAGE_NAME*@version:1.0*///简单选择排序publicclasstest01{//这是一个m......
  • 排序算法
    1.插入排序voidinsert_sort(){for(inti=1;i<n;i++){intx=a[i];intj=i-1;while(j>=0&&x<a[j]){a[j+1]=a[j];j--;}a[j+1]=x;}......
  • JQ拖拽排序
    /***TableDnDplug-inforJQuery,allowsyoutodraganddroptablerows*Youcansetupvariousoptionstocontrolhowthesystemwillwork*Copyright(c)DenisHowlett<[email protected]>*LicensedlikejQuery,seehttp://docs.jquery.com/L......
  • 冒泡排序
    目录汇编实现及推导过程高级语言实现纸上得来终觉浅，绝知此事要躬行汇编实现及推导过程;程序名称:;功能:冒泡排序，方法5：不用两两比较，第一位数和其余数比较，小就交换;=======================================assumecs:code,ds:data;排序;手推算法;;外层循环条件si=0;......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99