快速排序与冒泡排序的思路时候什么样的 - 黑马程序员技术交流社区

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]);
}
}
}
}

复制代码

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);
}
}
}
}
}

复制代码