Warning: Undefined array key "HTTP_REFERER" in
/www/wwwroot/prod/www.enjoyasp.net/wp-content/plugins/google-highlight/google-hilite.php on line
58
从小到大排序
1，冒泡：
当前元素是a[i]，在a[0]到a[i-1]之间依次比对
若a[j]> a[i]，a[j]与a[i]进行交换，（小值向上浮动,保证每次循环后a[0]获得最小值，a[1]二小）
因要与左侧元素比对，故循环从a[1]开始直到数据尾a[n-1]
2,选择：
当前元素是a[i],在a[i+1]与a[n-1]之间依次比对，取出最小值与a[i]进行交换。
以保证：第一次：比较n个元素，取出最小的放在第一个位置（进行交换）
第二次：比较剩下的n-1个元素，取出第二小的放在第二个位置
...
因要与右侧元素比对，故循环从a[0]开始到a[n-2]结束
3，插入：
当前元素是a[i]，在a[0]到a[i-1]之间依次比对,
若a[j] > a[i]，a[j]右移到a[j+1]
否则，说明当前位置的前一个位置正是要插入的位置，跳出循环，将a[i]的值放到a[j+1]处即可
（保证每次的a[i]都放在恰当的位置）
因要与左侧元素比对，故循环从a[1]开始直到数据尾a[n-1]
注：
(1)若n较小，可采用直接插入或直接选择排序。
但当记录规模较大时，因为直接选择移动的记录数少于直接插人，所以宜用选直接选择排序。
冒泡： 比较次数，频繁的交换操作
直接插入：比较次数，频繁的移位操作
选择： 比较次数，更少的交换操作
4，归并排序：递归拆分与合并。将数组拆分成左右数组，进行合并。
5 ,快速排序：
1）性质: 若一组数已经排好序，那么对于此组数每一个元素来说，每一个元素的左边都比它小，右边都比它大。
应用此性质：将当前元素放到恰好位置，让左区的元素都比它小，右区的元素都比它大，然后递归，
直到区细分到单个元素为止。
过程：对于数组第一个元素进行排序，循环：将左区元素第一个比当前元素大的与右区第一个比当前元素小的进行交换，
直到左区的都比当前元素小，右区的都比当前元素大。然后递归左区与右区。
2）快速排序也是使用了分治法的思路，不需要合并，快速排序和归并排序都是分治法，它们的区别在于，快速排序不需
要合并，快速排序的平均运行时间为Θ(n log n)
6，希尔排序，将整个无序列分割成若干小的子序列分别进行插入排序的方法，
是插入排序的一种高效稳定的改进版本。
先取一个正整数d1
快速排序
算法的实现：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication31
{
class Program
{
public delegate void Sort(int[] arr);
static void Main(string[] args)
{
int[] arr = { 9,8,7,6,5,4,3,2,1};
//BubbleSorter(arr);
//Printf("BubbleSorter", arr);
//SelectSorter(arr);
//Printf("SelectSorter", arr);
InsertSorter(arr);
Printf("InsertSorter", arr);
//Printf("QuickSort", arr, QuickSort);
//QuickSort(arr,0,arr.Length-1);
//Printf("QuickSort",arr);
Console.Read();
}
public static void Printf(string type,int[] arr) {
Console.WriteLine(string.Format("-------------------{0}-------------------",type));
DateTime DateTime = DateTime.Now;
//System.Threading.Thread.Sleep(1000);
//sort(arr);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < arr.Length; i++) {
sb.Append(","+arr[i].ToString() );
}
Console.WriteLine(sb.ToString().Substring(1,sb.Length-1));
string timespent = (DateTime.Now.Subtract(DateTime)).TotalMilliseconds.ToString();
Console.WriteLine(string.Format("-------------------{0}：{1}s----------------", type, timespent));
}
//冒泡法，每次将元素放到合适的位置，
//保持当前元素之前的元素处在有序状态，然后将当前元素与之前的有序元素进行对比交换
//复杂度：1+2+..(n-1) = (n-1)*n/2,比上边的复杂度少了一半。
//冒泡：即相邻数据的交换
private static int[] BubbleSorter(int[] arr)
{
int key = 0;
int tmp = 0;
for (int i = 1; i < arr.Length; i++) {
key = arr[i];
for (int j = i - 1; j >= 0; j--) {
if (arr[j] > key) {
tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
return arr;
}
//选择排序：
//第一次：比较n个元素，取出最小的放在第一个位置（进行交换）
//第二次：比较剩下的n-1个元素，取出第二小的放在第二个位置
// ......
//(n-1)*n/2加少量交换，而冒泡是(n-1)*n/2加多次交换
private static void SelectSorter(int[] arr)
{
int key = 0;
int k = 0;
for (int i = 0; i < arr.Length-1; i++)
{
k = i;
for (int j = i + 1; j < arr.Length; j++)
{
if (arr[j] < arr[k] )
{
k = j;
}
}
key = arr[i];
arr[i] = arr[k];
arr[k] = key;
}
}
/*
插入法，每次将元素放到最合适的位置，
保持当前元素之前的元素处在有序状态，然后将当前元素与之前的有序元素进行对比
若对比的元素大于当前元素，则将此对比的元素右移一位，若对比元素小于当前元素，说明此对比元素位置之后的那个
位置正是要插入的位置，插入即可
注：1,与增强版冒泡排序相同的一点是保持当前元素之前的元素处于有序状态，
然后逐个比较，满足条件的元素进行右移操作而不是交换。
2,参考打牌，拾起一张牌，放已排好顺序的牌堆中进行插入，右移每张牌直到找到比它小的，然后插入到之前即可。
//(n-1)*n/2加少量移位，比选择好一些
*/
private static void InsertSorter(int[] arr)
{
int key = 0;
int j = 0;
for (int i = 1; i < arr.Length; i++)
{
key = arr[i];
for (j=i-1; j >= 0; j--)
{
if (arr[j] > key)
{
arr[j + 1] = arr[j];
}
else { break; }
}
arr[j+1] = key;
}
}
///快速排序：利用的性质，若一个数组排好顺序，那么对于每一个元素来说，它左边的都比此元素小，右边的都比此元素大。
///过程，对于数组第一个元素进行排序，循环：将左区元素第一个比当前元素大的与右区第一个比当前元素小的进行交换，
///直到左区的都比当前元素小，右区的都比当前元素大。然后递归左区与右区。
///（若左区或右区进入对方区域，则说明循环完毕，跳出即可。）
///保证得到的结果是：它左边的元素都比此元素小，右边的元素都比此元素大
///然后分别从此元素左侧、若侧元素进行快速排序
private static void QuickSort(int[] arr, int left,int right) {
if (left >= right) { return; }
int i=left;
int j=right+1;
while (true)
{
while (i < arr.Length-1 && arr[++i] < arr[left]) ;
while (j >= 0 && arr[--j] > arr[left]) ;
if (i >= j) { break; }
else {
swap(ref arr[i], ref arr[j]);
}
}
swap(ref arr[left], ref arr[j]);
QuickSort(arr, left, j - 1);
QuickSort(arr, j + 1, right);
}
//交换两个数
static void swap( ref int left,ref int right) {
int tmp = left;
left = right;
right = tmp;
}
///
/// 归并排序：递归拆分与合并。将数组拆分成左右数组，进行合并。
int[] MeargeSort(int[] data)
{
//取数组中间下标
int middle = data.Length / 2;
//初始化临时数组let,right，并定义result作为最终有序数组
int[] left = new int[middle], right = new int[middle], result = new int[data.Length];
if (data.Length % 2 != 0)//若数组元素奇数个，重新初始化右临时数组
{
right = new int[middle + 1];
}
if (data.Length <= 1)//只剩下1 or 0个元数，返回，不排序
{
return data;
}
int i = 0, j = 0;
foreach (int x in data)//开始排序
{
if (i < middle)//填充左数组
{
left[i] = x;
i++;
}
else//填充右数组
{
right[j] = x;
j++;
}
}
left = MeargeSort(left);//递归左数组
right = MeargeSort(right);//递归右数组
result = Merge(left, right);//开始排序
//this.Write(result);//输出排序
return result;
}
///
/// 归并排序之并:排序在这一步
///
/// 左数组
/// 右数组
/// 合并左右数组排序后返回
int[] Merge(int[] a, int[] b)
{
//定义结果数组，用来存储最终结果
int[] result = new int[a.Length + b.Length];
int i = 0, j = 0, k = 0;
while (i < a.Length && j < b.Length)
{
if (a[i] < b[j])//左数组中元素小于右数组中元素
{
result[k++] = a[i++];//将小的那个放到结果数组
}
else//左数组中元素大于右数组中元素
{
result[k++] = b[j++];//将小的那个放到结果数组
}
}
while (i < a.Length)//这里其实是还有左元素，但没有右元素
{
result[k++] = a[i++];
}
while (j < b.Length)//右右元素，无左元素
{
result[k++] = b[j++];
}
return result;//返回结果数组
}
}
}
