- 浏览: 1205598 次
- 性别:
- 来自: 深圳
文章分类
- 全部博客 (718)
- HTML (13)
- JS基础 (23)
- JS应用 (40)
- AJAX (6)
- JSP相关 (12)
- JAVA基础 (52)
- JAVA应用 (74)
- APPLET (11)
- SWING\RCP (2)
- JAVA反射 (6)
- 设计模式 (26)
- 数据库设计 (20)
- Struts (35)
- Struts2 (12)
- Spring (22)
- Hibernate (45)
- Ibatis (18)
- mybatis (3)
- SSH (8)
- UML (5)
- WebService (3)
- XML (16)
- Log4j (7)
- WEB容器 (26)
- 数据结构 (36)
- Linux (34)
- Ruby on Rails (1)
- 其它技术 (27)
- IDE配置 (15)
- 项目实战 (2)
- Oracle (69)
- JAVA报表 (7)
- Android学习 (2)
- 博客链接 (1)
- 网络基础 (1)
- WEB集群 (1)
- .Net开发 (11)
- PB (4)
- 系统构建 (15)
最新评论
-
jnjeC:
牛逼啊哥们,讲得太好了
Maven仓库理解、如何引入本地包、Maven多种方式打可执行jar包 -
九尾狐的yi巴:
很好 感谢!
Itext中文处理(更新版) -
luweifeng1983:
有用的,重启一下嘛。
设置eclipse外部修改文件后自动刷新 -
Master-Gao:
设置了也不管用,怎么破呢?
设置eclipse外部修改文件后自动刷新 -
aigo_h:
锋子还有时间写博客,还是很闲哈!
Add directory entries问题
1、算法思想
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。
(1) 分治法的基本思想
分治法的基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。
(2)快速排序的基本思想
设当前待排序的无序区为R[low..high],利用分治法可将快速排序的基本思想描述为:
①分解:
在
R[low..high]中任选一个记录作为基准(Pivot),以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-
1)和R[pivotpos+1..high],并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字
pivot.key,右边的子区间中所有记录的关键字均大于等于pivot.key,而基准记录pivot则位于正确的位置(pivotpos)上,它无
须参加后续的排序。
注意:
划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注意pivot=R[pivotpos]):
R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
其中low≤pivotpos≤high。
②求解:
通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
③组合:
因为当"求解"步骤中的两个递归调用结束时,其左、右两个子区间已有序。对快速排序而言,"组合"步骤无须做什么,可看作是空操作。
2、快速排序算法QuickSort
using System;
using System.Collections.Generic;
using System.Text;
namespace ExQuickSorter
{
class QuickSorter
{
private void swap(ref int l, ref int r)
{
int temp;
temp = l;
l = r;
r = temp;
}
public void Sort(int[] list, int low, int high)
{
int pivot;//存储分支点
int l, r;
int mid;
if (high <= low)
return;
else if (high == low + 1)
{
if (list[low] > list[high])
swap(ref list[low], ref list[high]);
return;
}
mid = (low + high) >> 1;
pivot = list[mid];
swap(ref list[low], ref list[mid]);
l = low + 1;
r = high;
do
{
while (l <= r && list[l] < pivot)
l++;
while (list[r] >= pivot)
r--;
if (l < r)
swap(ref list[l], ref list[r]);
} while (l < r);
list[low] = list[r];
list[r] = pivot;
if (low + 1 < r)
Sort(list, low, r - 1);
if (r + 1 < high)
Sort(list, r + 1, high);
}
static void Main(string[] args)
{
int[] iArrary = new int[] { 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 };
QuickSorter q = new QuickSorter();
q.Sort(iArrary, 0, 13);
for (int m = 0; m <= 13; m++)
Console.WriteLine("{0}", iArrary[m]);
}
}
}
发表评论
-
排序算法与查找算法
2014-09-01 10:17 357八大排序算法: http://blog.csdn.net ... -
用递归与非递归实现斐波拉希数列
2013-05-15 00:46 1866如下: package com.test; publ ... -
利用LinkedList制作一个栈
2012-12-19 21:55 841import java.util.LinkedList; ... -
递归问题求解学习一
2009-04-22 14:12 696http://blog.csdn.net/lixiaoshan ... -
算术逻辑推理学习
2009-04-23 15:52 961数字推理考察的是对 ... -
由递归所想到的:如何将字符串或者数字转换成大写货币的问题
2009-04-24 11:54 1181这个问题同事在面试的时候遇到过,最近在看有关递归的问题时 h ... -
数据结构基础--排序: 各种排序算法全分析
2009-05-06 11:35 1421http://www.cnblogs.com/ziyiFly/ ... -
数据结构-算法: 分配排序(基数分配排序法)
2009-05-06 11:41 1043http://www.cnblogs.com/ziyiFly/ ... -
数据结构-算法: 分配排序(箱分配排序)
2009-05-06 11:43 880http://www.cnblogs.com/ziyiFly/ ... -
数据结构-排序: 两路归并排序算法
2009-05-06 11:44 1690数据结构-排序: 两路归 ... -
数据结构-排序: 插入排序(直接插入排序法)
2009-05-06 11:45 1180数据结构-排序: 插入排 ... -
数据结构-算法: 插入排序(希尔排序法)
2009-05-06 11:45 1425数据结构-算法: 插入排 ... -
数据结构-排序: 选择排序(堆选择排序法)
2009-05-06 11:47 873数据结构-排序: 选择排 ... -
数据结构-排序: 交换排序(冒泡排序法)
2009-05-06 11:47 1007数据结构-排序: 交换排序(冒泡排序法) 冒泡排序(Bu ... -
数据结构-排序: 选择排序(直接选择排序法)
2009-05-06 11:48 943数据结构-排序: 选择排序(直接选择排序法) 直接选择排 ... -
C#实现--单链表(链式)
2009-05-06 11:49 1359C#实现--单链表(链式) using Syste ... -
C#实现二叉树(三元素式)及二叉树遍历的四种方法
2009-05-06 11:50 1430C#实现二叉树(三元素式) ... -
JAVA排序类汇总
2009-05-06 11:54 1166package com.softeem.jbs.lesson4 ... -
谈谈防 SQL 注入式攻击策略
2009-05-07 09:30 1391谈谈防 SQL 注入式攻击 ... -
二进制数转换为八进制, 十六进制数的算法
2009-05-07 09:44 1277using System; using System.Col ...
相关推荐
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
数据结构中排序总结:冒泡、交换、选择、插入、基数、Shell、快速、归并、堆
8.3.2 快速排序 241 8.4 选择类排序 243 8.4.1 简单选择排序 243 8.4.2 堆排序 244 8.5 二路归并排序 247 8.6 基数排序 248 8.7 外部排序 252 8.7.1 概念与流程 252 8.7.2 置换-选择排序 253 8.7.3 佳归并树 254 ...
一趟快速排序的具体做法是:附设两个指针low和high,它们的初值分别指向数组第一个数据和最后一个数据,将枢轴记录暂存在R[0]的位置上排序过程中只作R[low]或R[high]的单向移动,直至一趟排序结束后再将枢轴记录移至...
排序是计算机程序设计中的一种重要...插入排序类、交换排序类、选择排序类、归并排序类和基数排序类。算法主要包括:插入排序、折半插入排序、选择排序、冒泡排序、希尔排序、快速排序、堆排序、归并排序、基数排序等。
改进快速排序以防止重复。 使插入排序与归并排序的交换实现兼容。 实现字符串类。 实现矢量模板。 通过节点类继承系统实现表达式计算器。 . 力码? 贡献 是时候从所有这些......东西中进行选择了!
直接插入排序,希尔排序,简单选择排序,冒泡排序,快速排序,堆排序,归并排序主要通过某种策略移动,选择或交换关键字来实现,关键字选择上,为了简便起见,都是整形数据。关键字间的比较,也都是直观的大小比较。...
希尔排序 交换排序:冒泡排序,快速排序 选择排序:简单选择排序,堆排序
本资源比较全面的包涵了各种排序,三种交换排序,选择排序,桶排序,归并排序,快速排序,二分法排序,等等
数据结构的快速排序法!是基础的东西,望大家多多支持!
排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序。 内部排序是数据记录在内存中进行排序。 而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要...
因为Linux与Windows不同,其后台运行着许多进程,所以强制关机可能会导致进程的数据丢失,使系统处于不稳定的状态,甚至在有的系统中会损坏硬件设备(硬盘)。在系统关机前使用 shutdown命令,系统管理员会通知所有...
学习数据结构和算法,了解其基本原理的同时,离不开编码实现,于是,尽力实现所学内容。 除此之外,在leetcode平台上,做一些算法题,一是巩固自己所学内容,二是强化自己的算法思想,三是查漏补缺。 项目结构 ...
数字排序法:通常来说有五大类方法:插入排序(直接插入排序、希尔排序等)、交换排序(冒泡排序、快速排序)、选择排序(简单选择排序、树形选择排序、堆排序)、归并排序、基数排序
实 验 报 告 实验名称 排序 课程名称 数据结构与算法实验 " " 专业班级:信息安全 学 号: 姓 名: 实验目的 掌握快速排序 实验内容 1、快速排序 编写程序,实现快速排序。从键盘上输入10个整数,存放在数组中,然后...
算法数据结构学习 (对应LeetCode编号) 时间复杂度 是否稳定排序 是否原地排序 冒泡怕排序 O(n^2) 是 是 插入排序 O(n^2) 是 是 选择排序 O(n^2) 否 是 快速排序 O(n*logn) 否 是 归并排序 O(n*logn) 是 否 计数排序 ...
\数据结构flash演示\版本2\10.3 交换排序-冒泡排序.swf \数据结构flash演示\版本2\10.3 快速排序.swf \数据结构flash演示\版本2\10.4.3 堆排序-删除.swf \数据结构flash演示\版本2\10.4.3 堆排序-插入.swf \数据...
1、本演示程序对以下6种常用的内部排序算法进行实测比较:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 2、待排序表的表的元素的关键字为整数,表长不小于100;其中的数据要用伪随机数产生...
使用MFC单文档实现数据结构8种排序算法的图形界面动态演示,更加形象的展示排序过程,八种排序算法包括插入排序(直接插入排序、折半插入排序、希尔排序)、选择排序(直接选择排序、堆排序)、交换排序(冒泡排序、...
3. **快速排序**:一种分治算法,通过选择一个“基准”值将数据分为两部分,一部分数据比基准值小,另一部分数据比基准值大,然后递归地对这两部分数据进行快速排序操作。 此外,该资源包还可能包含其他经典的数据...