首页 > 代码库 > 排序 交换排序
排序 交换排序
交换排序
思想：两两比较待排序记录的关键字，发现两个记录的次序相反时，即进行交换。
冒泡排序
1).基本思想：将被排序的记录的关键字垂直排列，首先将第一个记录的关键字与第二个记录的关键字进行比较，若前者大于后者，则交换两个记录，然后比较第二个和第三个记录，以此类推，直到第n-1个记录与第n个记录的关键字比较为止。上述过程称为第一趟冒泡排序，其结果使得关键字最大的记录被安排在最后一个记录的位置上。然后进行第二趟冒牌排序，对前n-1个记录进行同样的排序，使得关键字次大的记录被安排在第n-1个记录的位置上。在冒泡的过程中，关键字较小的记录像水中的气泡一样逐渐向上漂浮，而关键字较大的记录好像石块逐渐向下下沉，每次有一块最大的石块沉到底。
2）时间复杂度：O（n2）
代码实现：
/// <summary>
/// 冒泡排序
/// </summary>
/// <paramname="arr"></param>
///<returns></returns>
public static int[]bubbleSort(int[] arr)
{
for (int i = 0; i< arr.Length; i++)
{
for (int j =arr.Length-1; j >i; j--)
{
if (arr[j]< arr[j - 1])
{
int t= arr[j];
arr[j]= arr[j - 1];
arr[j- 1] = t;
}
}
}
return arr;
}
/// <summary>
/// 优化冒泡排序
/// </summary>
/// <paramname="arr"></param>
///<returns></returns>
public static int[]yhBubbleSort(int[] arr)
{
for (int i = 0; i< arr.Length; i++)
{
bool exchange= false;
for (int j =arr.Length - 1; j > i; j--)
{
if (arr[j]< arr[j - 1])
{
int t= arr[j];
arr[j]= arr[j - 1];
arr[j- 1] = t;
exchange = true;
}
}
if (!exchange)
break;
}
return arr;
}
2.快速排序
快速排序是一种分区交换排序。他采用了一种分治法策略，分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。快速排序时目前已知的平均速度最快的一种排序方法。
基本思想：从待排序的n个记录中任意选取一个记录Ri（通常选取序列中的第1个记录）作为标准，调整序列中各个记录的位置，使排在Ri前面的记录的关键字都小于Ri的关键字，排在Ri后面的记录的关键字都大于Ri的关键字，我们把这样一个过程称为一次快速排序。在第一次快速排序中，确定了所选的记录Ri最终在序列中的排序位置，同时也把剩余的记录分成了2个子序列。对2个子序列分别进行快速排序，又确定了2个记录在序列中应处的位置，并将剩余的记录分成4个子序列，如此往复下去，当各个子序列的长度为1时，全部记录排序完毕。
示例如下：
设置2个指示器，一个指示器low，指向顺序表的低端（第一个记录所在的位置），一个指示器high，指向书序表的高端（最后一个记录所在位置）。设置2个变量I,j,他们的初值为当前待排序子序列中第一个记录位置好low的下一条记录和最后一条记录的位置号high。将第一个记录作为标准放到临时变量pivot中，使它所占的位置腾空，然后从子序列的两端开始逐步向中间扫描，在扫描的过程中，变量i，j代表当前扫描到左、右两端记录在序列中的位置号。
1） 从序列的左端扫描时，从序列的当前左端i处开始，将标准记录的关键字与Ri的关键字比较，若前者大于等于后者，令i=i+1，继续进行比较，直到i=j或者小于后者。
2） 在序列右端扫描时，从序列的当前右端开始，把标准记录的关键字与记录Rj的关键字比较，若前者小于等于后者，令j=j-1，继续比较，如此下去，直到标准记录的关键字大于Rj的关键字或i大于j（此时所有位置好大于j的记录的关键字都大于标准记录的关键字）。
3） 如果i小于j，交换位置i和j的值。
上述过程反复交替执行，当i≥j时，扫描结束，j便为第1个记录在序列中应放置的位置。
如图所示：
在图中的排序过程中，首先从左向右移动，搜索大于标准值的第1个元素，i=4的位置所对应的元素80大于标准值70；从列表的右端开始，从右向左移动，搜索小于或等于标准值的第1个元素，这里i=10的位置所对应的元素45小于标准值；因为i<j，所以交换i=4和i=10位置上的元素值。这样就完成了第一趟排序的第一次交换。接着继续第二次交换，第二次交换发生在i=6和j=9的位置上，这时他们的值分别为90和60，交换后的结果如果进行二次交换后的那一行所示；接着i继续移动，当i=7时所对应的元素值100大于标准值70，i停止移动，j开始移动，当j移动到6的位置时，j小于i了，这时循环终止。交换标准值和j所在位置的值，完成一趟快速排序。
快速排序的算法的执行时间取决于标准记录的选择。如果每次排序时，所选记录的关键字的值都是当前子序列的“中间数”，那么该记录的排序终止位置在该子序列的中间，这样就把原来的子序列分解成了两个长度基本相等的更小的子序列，在这种情况下，排序的速度最快。最好情况下快速排序的时间复杂度为O（nlog2n）
另一种极端的情况是每次选取的记录的关键字都是当前子序列的“最小数”，那该记录的位置不变，它把原来的序列分成一个空序列和一个长度为原来序列长度减1的子序列，这种情况下时间复杂度为O(n2)。因此若原始记录列序列已“正序”排列，且每次选取的记录都是序列中的第1个记录，即序列中关键字最小的记录，此时，快速排序就变成了“慢速排序”。
由此可见，快速排序时记录的选取是非常重要的，在一般情况下，序列中的各记录的关键字的分布是随机的，所以每次选取当前序列中的第1个记录不会影响算法的执行时间，因此算法的平均比较次数为O（nlog2n）。
快速排序是一种不稳定的排序方法。
代码实现：
///<summary>
/// 快排
/// </summary>
/// <paramname="arr"></param>
/// <paramname="low"></param>
/// <param name="high"></param>
public static void fastSort( ref int[]arr,int low,int high)
{
if (low > high)
{
return;
}
int pivot = arr[low];
int i = low + 1;
int j = high;
int temp;
while (i < j)
{
while (i < j &&arr[i] <= pivot)
{
i++;
}
while (j >= i &&arr[j] >= pivot)
{
j--;
}
if (i < j)
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
if (low < j)
{
temp = arr[low];
arr[low] = arr[j];
arr[j] = temp;
}
fastSort(ref arr, low, j - 1);
fastSort(ref arr, j + 1, high);
}
本文出自 “虎哥的博客” 博客，请务必保留此出处http://7613577.blog.51cto.com/7603577/1559294
排序 交换排序