一、前言
主要讲述冒泡法排序和快速排序的基本流程,并给出代码实现,亲测可用。
二、冒泡法排序
冒泡法排序主要是将相邻两个值比较,把小的向前冒泡,大的向后沉淀,时间复杂度为O(n2)。主要思想如下:
分为内外循环,每次外循环确定一个大的数据的具体位置,如下实例:
从图中可以看出,进过两次外循环就可以得到排序结果,随后的8次循环都浪费了,为了避免这种情况,我们可以设置一个状态参数,用来表示内循环是否发生数据的交换,从而作为外循环是否退出的信号。
三、快速排序
快速排序是最有效的排序方法之一,其主要思想是对数据进行分开排序,通过选择一个基数,然后将所要排序的数据分成两部分,一边全大,一边全小。然后利用递归的思想对分开的数据继续排序。
四、代码实现
冒泡法排序(输出排序后数据在原数据中的位置):
void SparseGraphic::BubbleSort(const cv::Mat inMat, QVector<int> &index, cv::Mat &outMat)
{
if(inMat.rows!= )
return;
int col = inMat.cols;
index = QVector<int>(col);
for(int i = ;i<col;i++)
{
index[i] = i;
}
if(inMat.type()!= CV_32F)
inMat.convertTo(inMat,CV_32F);
outMat = inMat.clone(); float *ptr = outMat.ptr<float>();
float tmpVal;
int tmpIdx;
for(int i = ;i<col;i++)
{
for(int j = ;j<col - i -;j++)
{
if(ptr[j]>ptr[j+])
{
tmpVal = ptr[j];
ptr[j]=ptr[j+];
ptr[j+]=tmpVal;
tmpIdx = index[j];
index[j] = index[j+];
index[j+] = tmpIdx;
}
}
}
}
快速排序(输出排序后数据在源数据中的位置):
void SparseGraphic::QuickSort(cv::Mat inMat, QVector<int> &index, int low,int high)
{
if(inMat.rows!=)
return;
float *ptr = inMat.ptr<float>();
if(low < high)
{
int i = low,j = high;
float X = ptr[low];
while(i<j)
{
while(i<j && ptr[j] >= X)
j--;
if(i<j)
{
ptr[i++] = ptr[j];
int tmp = index[j];
index[j] = index[i-];
index[i-] = tmp;
} while(i<j && ptr[i] < X)
i++;
if(i<j)
{
ptr[j--] = ptr[i];
int tmp = index[i];
index[i] = index[j+];
index[j+] = tmp;
}
}
ptr[i] = X;
QuickSort(inMat,index,low,i-);
QuickSort(inMat,index,i+,high);
}
}
8. 冒泡法排序和快速排序(基于openCV)的更多相关文章
-
【Java基础】选择排序、冒泡法排序、二分法查找
1.选择排序: //改进后的选择排序,减少交换的次数 public static void sortSelect(int arr[]) { //用于存放最小数的下标 int s; for (int i ...
-
Java温故而知新-冒泡法排序
冒泡法排序是各种初学者在学习数组与循环结构时都会练习的一种简单排序算法. 冒泡法的精髓在于比较相邻的两个元素,较大的元素会不断的排到队伍后面去,就像水里的泡泡一样不断向上跑. 想像一下倒在一个透明玻璃 ...
-
Python 冒泡法排序
def sequence(disorder='', separators=''): arrays = disorder.split(separators) def desc(): for i in r ...
-
C#冒泡法排序源码
如下内容内容是关于C#冒泡法排序的内容,应该对码农有一些用途. int[] myArray = new int[] { 10, 8, 3, 5, 6, 7, 4, 6, 9 }; for( int j ...
-
[python,2018-01-15] 冒泡法排序
想写一个冒泡法排序,没什么思路,就先写了个java的 public static void main(String[] args) { int array[] = {88,2,43,12,34,8,6 ...
-
C语言 &#183; 冒泡法排序
算法提高 冒泡法排序 时间限制:1.0s 内存限制:512.0MB 输入10个数,用“冒泡法”对10个数排序(由小到大)这10个数字在100以内. 样例输入 1 3 6 8 2 7 ...
-
C程序数组算法 — 冒泡法排序【前冒 || 后冒】
第一种写法(前冒泡): /* C程序数组算法 - 冒泡法排序 * 此例子按照 大 -> 小 排序 * 原理:两两相比较,然后进行大小对调 * 比较次数: n^2 次 * 说明:冒泡排序是相对稳定 ...
-
冒泡法排序_c++实现
看完了郝斌老师的c语言视频,冒泡法排序,就试着写了.我觉得学习算法最重要的不是代码,而是它的原理. 代码: /** 2 * Copyright (c) 1991 - 2016 Arvin Tang. ...
-
php 实现冒泡算法排序、快速排序、选择排序,插入排序
许多人都说 算法是程序的核心,一个程序的好于差,关键是这个程序算法的优劣.作为一个初级phper,虽然很少接触到算法方面的东西 .但是对于冒泡排序,插入排序,选择排序,快速排序四种基本算法,我想还是要 ...
随机推荐
-
Maximal Rectangle
很不好想的一道题,参考:http://blog.csdn.net/doc_sgl/article/details/11832965 分为两步:把原矩阵转为直方图,再用largest rectangle ...
-
C语言 第五章 循环结构练习
一.计算15+16+17 …98+99的和 for实现 #include "stdio.h" void main() { //15+16+17 …98+99 ; ;i<=;i ...
-
【经验】ansible 批量推送公钥
1.使用 ssh-keygen -t rsa生成密钥对 ssh-keygen -t rsa 2.推送单个公钥到远程机器 格式: ssh-copy-id -i ~/.ssh/id_rsa.pub use ...
-
jquery ui和jquery easy ui的区别
jquery ui 是jquery开发团队 开发,适用于网站式的页面.jquery easyui 是第三方基于jquery开发,适用于应用程序式的页面. 两者的方法调用也略有不同:jquery ui ...
-
FLASH CC 2015 CANVAS (六)如何像FLASH那样实现场景(多canvas)
注意 此系列贴 为个人边“开荒”边写,所以不保证就是最佳做法,也难免有错误! 正式教程会在后续开始更新. swf 项目中,我们可以很容易在一个fla文档里创建多场景.也可以通过多个fla文件发布多个s ...
-
svn强制添加注释脚本
@echo off setlocal set SVN_BINDIR=C:/Program Files/VisualSVN Server/bin/ set REPOS=%1 set TXN=%2 rem ...
-
C#操作xml的3种方式
C#操作Xml有很多种方式,这里写出个人常使用的三种方式 XmlDocument DataSet linq to xml 首先声明本次操作使用的xml文件:books.xml:内容如下 <?x ...
-
ContentResolver,ContentProvider,ContentObserver使用记录
版权声明:本文出自汪磊的博客,转载请务必注明出处. 本篇博客只是记录一下ContentProvider的使用(这部分工作中用的比较少总是忘记),没有太深入研究.已经熟练掌握使用方式,想深入了解内部机制 ...
-
css写的常见图形
.aly-tooltip { display: inline-block; padding: 5px; padding-left: 15px; padding-right: 15px; backgro ...
-
通过实例介绍Android App自动化测试框架--Unittest
1.为什么需要使用框架实现自动化测试 作为测试工程师,可能在代码能力上相比开发工程师要弱一点,所以我们在写脚本的时候就会相对容易的碰到更多的问题,如果有一个成熟的框架供给我们使用的话,可以帮助我们避免 ...