首页 > 其他分享 >基础排序

基础排序

时间：2023-08-28 16:13:16浏览次数：40  
标签：arr temp int void 基础 mid 排序

选择排序

指针表示法
void choose_sort(int* 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, minIndex, i);
    }
}

数组表示法
void selectionSort(int 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,minIndex);
	}
}

冒泡排序

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

模板（泛型）

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,minIndex);
	}
}
甚至可以对自定义类型进行排序，如定义结构体：
struct Student {
    string name;
    int score;
    
    重载 < 号，为了自定义排序。
    bool operator<(const Student& otherStudent) {
        return score < otherStudent.score;
    }
    
	重载 << 输出，cout直接输出student结构体类型。
    friend ostream& operator<<(ostream& os, const Student& student) {
        os << "student:" << student.name << " " << student.score << endl
        return os;
    }
};

随机生成算法

<ctime> <cassert> <iostream>
assert 如果出现错误则中止，需要头文件包含 <cassert>
int* generateRandomArray(int n, int rangeL, int rangeR) {
    assert(rangeL <= rangeR);
    int* arr = (int*)malloc(sizeof(int) * n);
    srand((unsigned)time(NULL));
    for (int i = 0; i < n; i++) {
        *(arr + i) = rand() % (rangeR - rangeL + 1) + rangeL;
    }
    return arr;
}

插入排序

普通的插入排序，只是交换。
void insertSort(int* 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,j-1);
			}
		}
	}
}

加强插入排序，仅仅当arr[j-1] 比 arr[j] 大的时候才修改 ，交换改成赋值。
设定一个temp为 arr[i]，如果arr[j-1] 比 temp大，就说明该进行插入排序，直到后退到该放置temp的位置，然后内循环结束，在arr[j]处放置 temp。

void insertSort(int* arr,int n){
	for(int i=1;i<n;i++){
		int temp = arr[i];
		int j;
		for(j=i;j>0 && arr[j-1] > temp;j--){
			arr[j] = arr[j-1];
		}
		arr[j] = temp;
	}
}

迄今为止，学了三种基础排序，插入排序可以进行优化。
冒泡排序最慢、选择排序次之、插入排序再次之。（在一个基本有序的数列中，插入排序的速度有时比O(NlogN)的排序算法还快。

归并排序

void mergeSort(int* arr,int n);
void process(int* arr,int L,int R);
void merge(int* arr,int L,int mid,int R);

void mergeSort(int* arr,int n){
	process(arr,0,n-1);
}

void process(int* arr,int L,int R){
	if(L >= R){
		return;
	}
	int mid = L + ((R-L)>>1);
	process(arr,L,mid);
	process(arr,mid+1,R);
	merge(arr,L,mid,R);
}

void merge(int* arr,int L,int mid,int R){
	int size = R-L+1;
	新建数组
	int* temp = (int*)malloc(sizeof(int)*size);
	int p1 = L;
	int p2 = mid+1;
	int i = 0;
	while(p1 <= L && p2 <= R){
		temp[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
	}
	while(p1 <= mid){
		temp[i++] = arr[p1++];
	}
	while(p2 <= R){
		temp[i++] = arr[p2++];
	}
	for(i=0;i<size;i++){
		arr[L+i] = temp[i];
	}
}

快速排序

// 快速排序
int partition(int* arr, int L, int R);
void quick(int* arr, int L, int R);
void quickSort(int* arr,int n);

void quickSort(int* arr, int n) { 
	quick(arr, 0, n - 1); 
	return;
}

int partition(int* arr, int L, int R) {
    // 设置基准
    int temp = arr[L];
    int front = L;
    
    for (int rear = L + 1; rear <= R; rear++) {
        if (arr[rear] < temp) {
            swap(arr, rear, ++front);
        }
    }
    swap(arr, L, front);
    return front;
}

void quick(int* arr, int L, int R) {
    if (L >= R) {
        return;
    }
    int p = partition(arr, L, R);
    quick(arr, L, p - 1);
    quick(arr, p + 1, R);
}

小结：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 5000000

void swap(int* arr, int i, int j) {
    int temp = *(arr + i);
    *(arr + i) = *(arr + j);
    *(arr + j) = temp;
}

// 快速排序

int partition(int* arr, int L, int R);
void quick(int* arr, int L, int R);

void quickSort(int* arr, int n) { quick(arr, 0, n - 1); }

int partition(int* arr, int L, int R) {
    // 设置基准
    int temp = arr[L];

    int front = L;

    for (int rear = L + 1; rear <= R; rear++) {
        if (arr[rear] < temp) {
            swap(arr, rear, ++front);
        }
    }
    swap(arr, L, front);
    return front;
}

void quick(int* arr, int L, int R) {
    if (L >= R) {
        return;
    }
    int p = partition(arr, L, R);
    quick(arr, L, p - 1);
    quick(arr, p + 1, R);
}

// 交换
void insertSort(int* 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, j - 1);
            }
        }
    }
}

// 赋值代替交换
void insertSortPro(int* arr, int n) {
    for (int i = 1; i < n; i++) {
        int e = arr[i];  // 临时保存
        int j;           // 保存元素e应该插入的位置
        for (j = i; j > 0 && arr[j - 1] > e; j--) {
            arr[j] = arr[j - 1];
        }
        arr[j] = e;
    }
}

// 选择排序
void selectionSort(int* arr, int n) {
    for (int i = 0; i < n; i++) {
        int minIndex = i;
        for (int j = 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        swap(arr, i, minIndex);
    }
}

// 冒泡排序
void bubbleSort(int* arr, int n) {
    for (int i = n - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
            }
        }
    }
}

// 复制数组
int* copyIntArray(int* arr, int n) {
    int* newArr = (int*)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        *(newArr + i) = *(arr + i);
    }
    return newArr;
}

// 打印数组
void print(int* arr, int n) {
    for (int i = 0; i < n; i++) {
        if (i % 10 == 0) {
            printf("\n");
        }
        printf("%d\t", *(arr + i));
    }
    printf("\n");
}

// 按照长度和范围随机构建数组
int* getArr(int size, int randL, int randR) {
    srand((unsigned)time(NULL));
    int* arr = (int*)malloc(sizeof(int) * size);
    for (int i = 0; i < size; i++) {
        *(arr + i) = rand() % (randR - randL + 1) + randL;
    }
    return arr;
}

void merge(int* arr, int L, int mid, int R);
void process(int* arr, int L, int R);

void mergeSort(int* arr, int n) {
    process(arr, 0, n - 1);
    return;
}

void process(int* arr, int L, int R) {
    if (L >= R) {
        return;
    }
    int mid = L + ((R - L) >> 1);
    process(arr, L, mid);
    process(arr, mid + 1, R);
    merge(arr, L, mid, R);
}

void merge(int* arr, int L, int mid, int R) {
    // 创建一个 （R-L+1) 长度的数组
    int size = R - L + 1;
    int* newArr = (int*)malloc(sizeof(int) * size);

    for (int i = L; i <= R; i++) {
        newArr[i - L] = arr[i];
    }

    // 开始排序
    int front = L;
    int rear = mid + 1;
    int i = 0;
    while (front <= mid && rear <= R) {
        newArr[i++] = arr[front] < arr[rear] ? arr[front++] : arr[rear++];
    }
    while (front <= mid) {
        newArr[i++] = arr[front++];
    }
    while (rear <= R) {
        newArr[i++] = arr[rear++];
    }
    for (i = 0; i < size; i++) {
        arr[i + L] = newArr[i];
    }
}

int* generateNearlyOrderedArray(int n, int count) {
    srand((unsigned)time(NULL));
    int* arr = (int*)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        arr[i] = i + 1;
    }
    for (int j = 0; j < count; j++) {
        int p1 = rand() % n;
        int p2 = rand() % n;
        swap(arr, p1, p2);
    }
    return arr;
}

void test01() {
    clock_t begin;
    clock_t end;
    double time;
    int* arr1 = getArr(N, 0, N);
    int* arr2 = copyIntArray(arr1, N);
    int* arr3 = copyIntArray(arr1, N);
    int* arr4 = copyIntArray(arr1, N);
    int* arr5 = copyIntArray(arr1, N);

    // 计算归并排序时间
    printf("\n");
    begin = clock();
    mergeSort(arr5, N);
    end = clock();
    time = end - begin;
    time = time / CLOCKS_PER_SEC;
    printf("mergeSort:\t%10lf s\n", time);

    // 计算插入排序（落后）时间

    begin = clock();
    insertSort(arr1, N);
    end = clock();
    time = end - begin;
    time = time / CLOCKS_PER_SEC;
    printf("insertSort:\t%10lf s\n", time);

    // 计算插入排序（改进）时间
    begin = clock();
    insertSortPro(arr2, N);
    end = clock();
    time = end - begin;
    time = time / CLOCKS_PER_SEC;
    printf("insertSortPro:\t%10lf s\n", time);

    // 计算选择排序时间
    begin = clock();
    selectionSort(arr3, N);
    end = clock();
    time = end - begin;
    time = time / CLOCKS_PER_SEC;
    printf("selectionSort:\t%10lf s\n", time);

    // 计算冒泡排序时间
    begin = clock();
    bubbleSort(arr4, N);
    end = clock();
    time = end - begin;
    time = time / CLOCKS_PER_SEC;
    printf("bubbleSort:\t%10lf s\n", time);

    printf("\n");

    free(arr1);
    free(arr2);
    free(arr3);
    free(arr4);
    free(arr5);
    arr1 = NULL;
    arr2 = NULL;
    arr3 = NULL;
    arr4 = NULL;
    arr5 = NULL;
}

void test02() {
    clock_t begin;
    clock_t end;
    double time;
    int* arr1 = generateNearlyOrderedArray(N, 2);
    int* arr2 = copyIntArray(arr1, N);
    int* arr3 = copyIntArray(arr1, N);
    int* arr4 = copyIntArray(arr1, N);
    int* arr5 = copyIntArray(arr1, N);

    // 计算归并排序时间
    printf("\n");
    begin = clock();
    mergeSort(arr5, N);
    end = clock();
    time = end - begin;
    time = time / CLOCKS_PER_SEC;
    printf("mergeSort:\t%10lf s\n", time);

    // 计算插入排序（落后）时间

    begin = clock();
    insertSort(arr1, N);
    end = clock();
    time = end - begin;
    time = time / CLOCKS_PER_SEC;
    printf("insertSort:\t%10lf s\n", time);

    // 计算插入排序（改进）时间
    begin = clock();
    insertSortPro(arr2, N);
    end = clock();
    time = end - begin;
    time = time / CLOCKS_PER_SEC;
    printf("insertSortPro:\t%10lf s\n", time);

    // 计算选择排序时间
    begin = clock();
    selectionSort(arr3, N);
    end = clock();
    time = end - begin;
    time = time / CLOCKS_PER_SEC;
    printf("selectionSort:\t%10lf s\n", time);

    // 计算冒泡排序时间
    begin = clock();
    bubbleSort(arr4, N);
    end = clock();
    time = end - begin;
    time = time / CLOCKS_PER_SEC;
    printf("bubbleSort:\t%10lf s\n", time);

    printf("\n");

    free(arr1);
    free(arr2);
    free(arr3);
    free(arr4);
    free(arr5);
    arr1 = NULL;
    arr2 = NULL;
    arr3 = NULL;
    arr4 = NULL;
    arr5 = NULL;
}

int main() {
    clock_t begin;
    clock_t end;
    double time;
    int* arr1 = getArr(N, 0, N);
    int* arr2 = copyIntArray(arr1, N);

    // 计算归并排序时间
    printf("\n");
    begin = clock();
    mergeSort(arr1, N);
    end = clock();
    time = end - begin;
    time = time / CLOCKS_PER_SEC;
    printf("mergeSort:\t%10lf s\n", time);

    // 计算快速排序时间
    begin = clock();
    quickSort(arr2, N);
    end = clock();
    time = end - begin;
    time = time / CLOCKS_PER_SEC;
    printf("quickSort:\t%10lf s\n", time);
    printf("\n");

    free(arr1);
    free(arr2);

    arr1 = NULL;
    arr2 = NULL;
}

总结

快速排序大部分情况比归并排序还要快，在数组基本有序的情况下，优化过的插入排序比归并排序都要快。基础排序冒泡、选择都是非常慢的，O(N^2)级别的时间复杂度。
快速排序和归并排序是O(N logN)级别的。

标签：arr,temp,int,void,基础,mid,排序
From： https://www.cnblogs.com/zxinlog/p/17662561.html

相关文章

  • 堆排序
    堆是以二叉树为结构组成的一个序列，一般以数组进行实现，如设N=1为根节点，则左节点2*N，右节点2*N+1，以此构建一整个堆。堆结构体的数据结构typedefintItem;typedefstructmaxHeap{  Item*data; //堆的数组实现  intcount; //实际存在的数据量}maxHea......
  • 斩获“年度突破成果”奖！天翼云构建强大AI算力基础，制胜人工智能新时代
    8月18-19日，2023中国算力大会在宁夏银川举办。在大会“年度突破成果”发布环节，中国电信天翼云《基于异构多云环境下的息壤算力调度应用实践》荣获2023中国算力大会“算力中国·年度突破成果”奖，天翼云算力分发网络平台“息壤”的智能高效算力调度能力再次获得权威认可。 与大会......
  • 【校招VIP】前端算法考察之排序
    考点介绍：不同的场景中，不同的排序算法执行效率不同。稳定：冒泡、插入、归并不稳定：选择、快速、堆排序、希尔排序一、考点题目1、使用js实现数组的快速排序解答：快速排序使用了冒泡+分治的思路。每轮从数组中取出一个数作为基准；在排序过程中，小于或等于基准数的全部放到基准的左......
  • Pt.I 从零基础到音乐制作者的自学指南
    1音符1.14/8/16分音符4分音符代表一个节拍的时值,在4/4拍子中,4分音符就是一个拍.如果在速度为60BPM的情况下演奏4分音符,每个4分音符会持续1秒.8分音符是4分音符时值的一半,16分音符是8分音符的一半.1.2连音当两个或多个相同的音符连在一起时,......
  • 哈希表基础题217. 存在重复元素、389. 找不同、496. 下一个更大元素 I
    217. 存在重复元素1classSolution:2defcontainsDuplicate(self,nums:List[int])->bool:3#方法1：set去重，直接比较去重之后数组长度4iflen(set(nums))!=len(nums):5returnTrue6else:7return......
  • 04 以太网交换基础
    在网络中传输数据时需要遵循一些标准，以太网协议定义了数据帧在以太网上的传输标准，了解以太网协议是充分理解数据链路层通信的基础。以太网交换机是实现数据链路层通信的主要设备，了解以太网交换机的工作原理也是十分必要的。设备的工作模式单工模式：信号传递是单方向的，比如传统......
  • JVS低代码开发工具基础篇：应用中心配置说明
    JVS应用中心是一个集中管理和提供企业级轻应用程序的平台或界面。它可以是类似企业轻应用的应用商店或者一个软件管理工具，用于管理者便捷的下载、上传、发布和安装各种企业级应用程序。应用中心功能介绍在JVS角色中有“应用管理员”的角色，如果赋予该角色，则用户为应用管理员，应用管理......
  • CSS基础-2D变形
    变形是CSS3中比较颠覆性的特征之一，今天介绍四种2D变形旋转、缩放、倾斜、位移变形。变形在CSS3用 transform 属性来实现。transform-origin属性transform-origin表示旋转的原点，默认是在盒子的中心位置(center)。transform-origin的值可以是一个、两个或者三个，其中的每......
  • sql根据子表的条数排序
    您可以使用子查询和聚合函数来根据子表的条数排序，以下是一个示例：假设有两张表：orders和order_items，其中orders表包含订单信息，而order_items表包含每个订单的订单项信息。首先，您可以编写一个子查询来计算每个订单的订单项数量，并将其命名为order_item_count：SELECTorder_id,......
  • 凌蒙派-RK3568开发板-基础外设类：简易HDF驱动
    1、案例简介该程序是基于OpenHarmony标准系统编写的基础外设类：简易HDF驱动。目前已在凌蒙派-RK3568开发板跑通。详细资料请参考官网：https://gitee.com/Lockzhiner-Electronics/lockzhiner-rk3568-openharmony2、基础知识2.1、OpenHarmonyHDF开发简介HDF（HardwareDriverFoun......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99