快速排序与冒泡排序的思路时候什么样的

追溯客

本帖最后由 hourglass 于 2013-11-4 20:44 编辑

只需要说明思路就行，如果有直接的代码可以帖上，那就更好了。。

凤凰涅槃 · 凤凰涅槃

冒泡排序基本思路：将相邻的两个数据进行比较，把较小的数据交换到前面。在每一趟的比较中较小的数不断地向上"浮出"，而剩下数中的最大数会"沉到"最底下。

快速排序是对冒泡排序的一种改进。他的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，

则可分别对这两部分记录继续进行排序，以达到整个序列有序。

凤凰涅槃 · 凤凰涅槃

发现我上面回答的太空洞了，我自己看了以后，都不能懂。。。。。。
下面是我在网上看的一个博客园里面的文章，讲的很详细，希望能帮到你，他里面有好多关于排序文章你可以看看
http://www.cnblogs.com/luchen927/archive/2012/02/28/2367708.html

夏闯富 · 夏闯富

里面各种排序（冒泡、快速、希尔、插入、选择）代码都有，很详细！话说最重要的是用心看。
http://halcat.blog.163.com/blog/static/84964843201392711649696/

佟嘉豪 · 佟嘉豪

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace 冒泡排序
{
class Program
{
static void Main(string[] args)
{
int[] arrays = new int[] { 95, 45, 15, 78, 84, 51 };
//从小到大排序
for (int i=arrays.Length-1; i>0; i--)//比较的次数，是数组长度-1,也就是数组下标最大值
{
//j是数组的下标
//j<=i-1 是因为数组的最大下标是i
for (int j =0; j <= i-1; j++)
{
int temp = 0;
//用于相邻两个数的比较
if (arrays[j] > arrays[j + 1])//每走一次if 大小数交换 >是按从小到大 <是按从大到小
{
temp = arrays[j];
arrays[j] = arrays[j + 1];
arrays[j + 1] = temp;
}
}
}
for (int i = 0; i < arrays.Length; i++)
{
Console.WriteLine(arrays[i]);
}
}
}
}

复制代码

【冒泡排序】主要原理在内循环：（从小到大排序）
我们首先抛开外循环

主要看内循环
假设有6个数 6 5 4 3 2 1
首先6和5比较大的和小的交换
5 6 4 3 2 1
再让6和4 比较大的和小的交换
5 4 6 3 2 1
....
依次下去就会出现最大的数6 跑到最后
这时候当6跑到最后的时候，内循环终止了外循环也就相当于进行了1次
我们看上面的循环，一直都是最大数（6）在换位置直到最后
这时候我们发现 6个数比较了5次才让6到最大位置

外循环2次的时候
我们可以把最大数6抛出去
比较前5个
同理也是相邻两个比较直到5到最后
这时候我们发现5个数比较4次到最大位置
外循环3次
我们把最大数5抛出去比较前4个

.....
最后剩下2个的时候
2个数比较一次到最大位置

所以综上外循环执行一次，一个数就找到了位置，那么外循环一个执行了多少次呢，所以有几个数，外循环几次，就能固定所有数字的位置
假设有6个数，为什么不是6次，而是5次呢，因为当剩下2个数的时候，倒数第二大的位置固定，那么最小的数也同时固定了

佟嘉豪 · 佟嘉豪

哥们，为了写这个破狗屎，我屁股一下午没动地方了= =！（其中递归那个地方还是不理解的）只不过用程序单调实现的

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace 快速排序
{
class Program
{
/// <summary>
/// 现学现卖
/// </summary>
/// <param name="args"></param>
static void Main(string[] args)
{
int[] s = new int[] { 72, 6, 57, 88, 60, 42, 83, 73, 48, 85 };
//int[] s = new int[] { 32, 21, 47,37 };
QuikSort(s, 0, s.Length - 1);
for (int i = 0; i < s.Length; i++)
{
Console.WriteLine(s[i]);
}
}
//快分就是以数组s[0]为基数key，从右面开始找到s[j ]比key小的填到s[0],再从左面s[1]找到s[i]比key大填到s[j]
//从右面s[j-1]找到新s[j] 比key小的填到s[i],再从左面s[i+1]找到新s[i] 比key大填到s[j]
//知道i 和 j碰上了那么说明左面没有比key大的右面没有比key小的
//关键点在于找到的同时，放到另一侧
//这个方法是把数组以key为基数，分成两部分，左面比key小，右面比key大
//并返回分组后,key的新下标，注意key为s【le】
public static int FindKeyIndex(int[] s, int le, int rg)//le,rg都是数组下标
{
int k = 0;//用于返回的key的坐标
int key = s[le];//每次都默认s[le]为key 相当于把这个位置空出来
int i = le;//i代表从前往后找找比key大的
int j = rg;//j代表从后往前找找比key小的
while (i < j)//如果就1个数，没必要排序
{
//首先一定要从右往左找
while (true)
{
//这个if一定要写
//开始我没写，结果有一个数排序错误，当i=3,j=4的时候，
//s[4]确实大于s[3] 结果j--了
//判断s[3]=key,i++了
//导致i比j大做了后面的从左往右找
//这就和i与j相遇停止查找这个事实矛盾了，后续情况没再跟进
if (i == j)
{
break;
}
if (s[j] <= key)
{
s[i] = s[j];
i++;
break;
}
else
{
j--;
}
}
//从左往右找
while (true)
{
if (i == j)
{
break;
}
if (s[i] >= key)
{
s[j] = s[i];
j--;
break;
}
else
{
i++;
}
}
}
s[i] = key;
k = i;
return k;//这个下标是用来进行接下来以k 为基准的左右两面的排序
}
//递归排序数组
public static void QuikSort(int[] s, int le, int rg)
{
if (le < rg)//如果数组中就一个元素，也不用排了
{
int index = FindKeyIndex(s, le, rg);
if (index - 1 != 0)//如果index==1，那左面不用排了
{
QuikSort(s, le, index - 1);
}
if (index + 1 < rg)//如果index右面也剩下一个，也不用排了
{
QuikSort(s, index + 1, rg);
}
}
}
}
}

复制代码

佟嘉豪 · 佟嘉豪

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace 快速排序
{
class Program
{
/// <summary>
/// 现学现卖
/// </summary>
/// <param name="args"></param>
static void Main(string[] args)
{
int[] s = new int[] { 72, 6, 57, 88, 60, 42, 83, 73, 48, 85 };
//int[] s = new int[] { 32, 21, 47,37 };
QuikSort(s, 0, s.Length - 1);
for (int i = 0; i < s.Length; i++)
{
Console.WriteLine(s[i]);
}
}
//快分就是以数组s[0]为基数key，从右面开始找到s[j ]比key小的填到s[0],再从左面s[1]找到s[i]比key大填到s[j]
//从右面s[j-1]找到新s[j] 比key小的填到s[i],再从左面s[i+1]找到新s[i] 比key大填到s[j]
//知道i 和 j碰上了那么说明左面没有比key大的右面没有比key小的
//关键点在于找到的同时，放到另一侧
//这个方法是把数组以key为基数，分成两部分，左面比key小，右面比key大
//并返回分组后,key的新下标，注意key为s【le】
public static int FindKeyIndex(int[] s, int le, int rg)//le,rg都是数组下标
{
int k = 0;//用于返回的key的坐标
int key = s[le];//每次都默认s[le]为key 相当于把这个位置空出来
int i = le;//i代表从前往后找找比key大的
int j = rg;//j代表从后往前找找比key小的
while (i < j)//如果i j碰头了没必要继续了这时候就已经分开了
{
//首先一定要从右往左找
while (true)
{
//这个if一定要写
//开始我没写，结果有一个数排序错误，当i=3,j=4的时候，
//s[4]确实大于s[3] 结果j--了
//判断s[3]=key,i++了
//导致i比j大做了后面的从左往右找
//这就和i与j相遇停止查找这个事实矛盾了，后续情况没再跟进
if (i == j)
{
break;
}
if (s[j] <= key)
{
s[i] = s[j];
i++;
break;
}
else
{
j--;
}
}
//从左往右找
while (true)
{
if (i == j)
{
break;
}
if (s[i] >= key)
{
s[j] = s[i];
j--;
break;
}
else
{
i++;
}
}
}
s[i] = key;
k = i;
return k;//这个下标是用来进行接下来以k 为基准的左右两面的排序
}
//递归排序数组
public static void QuikSort(int[] s, int le, int rg)
{
if (le < rg)//如果数组中就一个元素，也不用排了
{
int index = FindKeyIndex(s, le, rg);
if (index - 1 != 0)//如果index==1，那左面不用排了
{
QuikSort(s, le, index - 1);
}
if (index + 1 < rg)//如果index右面也剩下一个，也不用排了
{
QuikSort(s, index + 1, rg);
}
}
}
}
}

复制代码

有一个地方注释写错了，重新穿了下

hourglass · hourglass

谢谢各位的回答，给的链接我会看的

帐号		自动登录	找回密码
密码			加入黑马

快速排序与冒泡排序的思路时候什么样的

评分

7 个回复

评分

评分

评分

评分

评分