排序算法-JZTXT

首先定义一个交换数组元素的方法，对于给定数组int arr[], 交换i位置跟j位置的元素可以用一下方法实现

void Swap(int[] arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

选择排序: 每次选择最小的元素跟未排序序列的第一个元素交换

public class Selection
{
    public static void Sort(int[] arr)
    {
        for (int i = 0; i < arr.Length; i++)
        {
            int minIndex = i;
            for (int j = i + 1; j < arr.Length; j++)
            {
                if (arr[j] < arr[minIndex])
                    minIndex = j;
            }
            Swap(arr, i, minIndex);
        }
    }
}

插入排序: 扫描整个数组，将每个元素都插入到适当的位置，当前元素左边的所有元素都是有序的，但最终位置还不固定，当遍历完整个数组，所有元素都是有序的

public class Insertion
{
    public static void Sort(int[] arr)
    {
        for (int i = 1; i < arr.Length; i++)
        {
            for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--)
            {
　　　　　　　　　　Swap(arr, j, j-1);
            }
        }
    }
}

希尔排序: 希尔排序是基于插入排序的一种改进，将下标按一定增量进行分组，对每组元素使用直接插入排序，当增量减至1时，整个数组就变成有序的

public class Shell
{
    public static void Sort(int[] arr)
    {
        for (int gap = arr.Length / 2; gap > 0; gap /= 2)
        {
            for (int i = gap; i < arr.Length; i++)
            {
                int j = i;
                while (j - gap >= 0 && arr[j] < arr[j - gap])
                {
                    Swap(arr, j, j - gap);
                    j -= gap;
                }
            }
        }
    }
}