using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace Sort{public class Sort{///<summary>/// 插入排序--稳定排序///</summary>///<param name="list"></param>public static void InsertSort(List<int> list){int j, tmp;for (int i =1; i < list.Count; i++){j = i;tmp = list[i];while (j >0&& tmp <= list[j -1]){list[j] = list[j -1];j--;}list[j] = tmp;}}///<summary>/// 希尔排序///</summary>///<param name="list"></param>public static void ShellSort(List<int> list){int j, tmp;int h =3;while (h>0){for (int i = h; i < list.Count; i++){tmp = list[i];j = i;while ((j > h -1) && tmp < list[j - h]){list[j] = list[j - h];j -= h;}list[j] = tmp;}h = (h -1) %3;}}///<summary>/// 冒泡排序--稳定排序///</summary>///<param name="list"></param>public static void BubbleSort(List<int> list){if (list ==null|| list.Count <1){return;}int tmp;for (int i =0; i < list.Count -1; ++i){bool flag=false;for (int j = list.Count -1; j >i+1; j--){if (list[j] > list[j +1]){tmp = list[j];list[j] = list[j +1];list[j +1] = tmp;flag=true;}if(flag==false){return;}}}}///<summary>/// 选择排序--直接选择排序///</summary>///<param name="list"></param>public static void SelectSort(List<int> list){int min, tmp;for (int i =0; i < list.Count; i++){min = i;for (int j = i +1; j < list.Count; j++){if (list[j] < list[min]){min = j;}}if (i != min){tmp = list[i];list[i] = list[min];list[min] = tmp;}}}///<summary>/// 堆排序///</summary>///<param name="list"></param>public static void HeapSort(List<int> list){int n = list.Count;for (int i = n/2-1; i >=0; i--){Sift(list, i, n -1);}for (int i = n -1; i >=1; i--){int tmp = list[0];//取堆顶元素list[0] = list[i];//让堆中最后一个元素上移到堆顶位置list[i] = tmp;//此时list[i]已不在堆中，用于存放排好序的元素Sift(list, 0, i -1);//重新调整堆}}private static void Sift(List<int> list, int low, int high)//建堆过程{//i为欲调整子树的根结点的索引号，j为这个结点的左孩子int i = low, j =2* i +1;int tmp = list[i];//记录双亲结点的值while (j<=high){//如果左孩子小于右孩子，则将欲交换的孩子结点指向右孩子if (j < high && list[j] < list[j +1]){j++;//j指向右孩子}if (tmp < list[j])//如果双亲结点小于它的孩子结点{list[i] = list[j];//交换双亲结点和它的孩子结点i = j;//以交换后的孩子结点为根，继续调整它的子树j =2* i +1;//j此时代表交换后的孩子结点的左孩子}else//调整完毕{break;}}list[i] = tmp;//使最初被调整的结点放入正确的位置}///<summary>/// 归并排序--稳定排序///</summary>///<param name="list"></param>///<param name="low"></param>///<param name="high"></param>public static void MergeSort(List<int> list, int low, int high){if (low < high){int mid = (low + high) /2;MergeSort(list, low, mid);MergeSort(list, mid +1, high);Merge(list, low, mid, high);}}private static void Merge(List<int> list, int low, int mid, int high){//listTmp为临时存放空间，存放合并后的数据List<int> listTmp =new List<int>(high - low +1);int i = low, j = mid +1, k =0;//k为listTmp的下标while (i <= mid && j <= high){listTmp[k++] = (list[i] < list[j]) ? list[i++] : list[j++];}while (i <= mid){listTmp[k++] = list[i++];}while (j <= high){listTmp[k++] = list[j++];}for (i = low, k=0; i <= high;i++,k++ ){list[i] = listTmp[k];}}///<summary>/// 快速排序///</summary>///<param name="list"></param>public static void QuickSort(List<int> list){QuickSort(list, 0, list.Count -1);}public static void QuickSort(List<int> list, int low, int high){if (low < high){int i = low, j = high, tmp = list[i];while (i < j){while (i < j && list[j] >= tmp){j--;}list[i] = list[j];while (i < j && list[i] <= tmp){i++;}list[j] = list[i];}list[i] = tmp;QuickSort(list, low, i -1);QuickSort(list, i +1, high);}}}}