常见查找和排序算法汇总

2024-02-13 21:56| 来源: 网络整理| 查看: 265

主要内容：

顺序查找、折半查找-------查找算法冒泡排序、简单选择排序、直接插入排序、希尔排序、归并排序、快速排序、堆排序------排序算法在这里插入图片描述

一、查找

1、顺序查找从最后一个记录开始，逐个进行比较，若相等则查找成功，否则查找失败。

//顺序查找 a[1 - len] int Sq_Search(int a[],int key,int len) { int i; //哨兵，使内循环不用判断数组是否越界，提高程序运行效率，减少查找时间 a[0] = key; for(i = len;a[i] != key;i--) ; return i; }

2、折半查找

在折半查找中，查找一个值相当于在一个满二叉树中查找，计算平均查找次数时可利用满二叉树性质。

//折半查找 a[0 - len-1] int Bi_Search(int a[],int key,int len) { int i,low,mid,high; low=0;high=len-1; while(low key) high = mid-1; else low = mid +1; } return -1; //查找失败返回-1 } 二、排序（升序）

1、冒泡排序

排序思想：从前往后依次比较前后两个相邻元素，将大的置于右端，小的置于左端；如此，每轮可以将一个值置于其最终位置，n-1轮后数组有序。

稳定性：稳定，当元素相等时，并不会发生交换空间效率：O(1) 平均情况：O(n^2) 最坏情况：O(n^2)，序列逆序时最优情况：O(n)，序列有序时

代码：

#include void swap(int &a,int &b) { int t; t = a; a = b; b = t; } void Bubble_Sort(int a[],int n) { int i,j; for(i = 0;i

【本文地址】

公司简介

联系我们