1、直接插入排序

冒泡排序属于插入排序。

排序最好情况：为正序，需进行 n-1 趟排序，进行 n-1 次比较和0次移动数据。
排序最坏情况：为逆序，需进行 n-1 趟排序，进行 n^2/2 次比较和 n^2/2 次移动数据。

平均比较次数：n^2/4
平均移动次数：n^2/4

平均时间复杂度：O(n^2)
平局空间复杂度：O(1)。因为只在交换位置时使用一个辅助空间做暂存记录。

2、C#实现

StraightInsert.cs

	public static class StraightInsertSort
    {
        public static void StraightInsert(int[] numbers)
        {
            if (numbers == null || numbers.Length < 2)
            {
                Console.WriteLine("参数数组有误");
                return;
            }

            int temp;
            for (int i = 1; i < numbers.Length; i++)
            {
                //判断新加入的元素不是最大的
                if (numbers[i] < numbers[i - 1])
                {
                    temp = numbers[i];
                    //把大于新元素的元素向前移动
                    int j;
                    //注意要先判断j>0，不然当j=0时判断numbers[j-1]会出现越界数组
                    //我就被这个坑了好一会儿
                    for (j = i; j > 0 && numbers[j-1] > temp ; j--)
                    {
                        numbers[j] = numbers[j-1];
                    }
                    //把新元素插入到应有的位置
                    numbers[j ] = temp;
                }

                for (int k = 0; k < numbers.Length; k++)
                {
                    Console.Write(numbers[k] + " ");
                }
                Console.WriteLine();
            }
        }
    }

Program.cs

	class Program
    {
        static void Main(string[] args)
        {
            int[] numbers = { 49, 38, 65, 97, 76, 13, 27, 49 };
            numbers = StraightInsertSort.StraightInsert(numbers);

            for (int i = 0; i < numbers.Length; i++)
            {
                Console.Write(numbers[i] + " ");
            }
            Console.WriteLine();

            Console.ReadKey();
        }
    }

3、C++实现

StraightInsertSort.cpp

///直接插入排序
class StraightInsertSort
{
public:
    static void StraightInsert(int numbers[],int length);
};

void StraightInsertSort::StraightInsert(int numbers[],int length)
{
    if (numbers == NULL || length < 2)
    {
        cout<<"参数数组有误"<<endl;
        return;
    }

    int temp;
    for (int i = 1; i < length; i++)
    {
        //判断新加入的元素不是最大的
        if (numbers[i] < numbers[i - 1])
        {
            temp = numbers[i];
            //把大于新元素的元素向前移动
            int j;
            //注意要先判断j>0，不然当j=0时判断numbers[j-1]会出现越界数组
            //我就被这个坑了好一会儿
            for (j = i; j > 0 && numbers[j-1] > temp ; j--)
            {
                numbers[j] = numbers[j-1];
            }
            //把新元素插入到应有的位置
            numbers[j] = temp;
        }


        for (int k = 0; k < length; k++)
        {
            cout << numbers[k] << " ";
        }
        cout << endl;
    }
}

main.cpp

int main()
{
    int numbers[] = {49,38,65,97,76,13,27,49};
    int length = sizeof(numbers)/sizeof(numbers[0]);

    StraightInsertSort::StraightInsert(numbers,length);

    for(int i=0;i<length;i++){
        cout<<numbers[i]<<" ";
    }
    cout<<endl;

    return 0;
}

4、lua实现

numbers = {49,38,65,97,76,13,27,49}

function BubbleSort(nums)
	local length = #nums
	if (nums == nil or length < 2) then
		print("参数数组有误")
		return
	end

	for i=2,length,1 do

		if(nums[i] < nums[i-1]) then
			local temp = nums[i]

			for j=i,1,-1 do
				if(j>1 and nums[j-1]>temp) then
					nums[j] = nums[j-1]
				else
					nums[j] = temp
					break
				end
			end
		end

		for k=1,length,1 do
			io.write(nums[k] .. ' ')
		end
		print()
	end
end

BubbleSort(numbers)

for i=1,#numbers,1 do
	io.write(numbers[i] .. ' ')
end
print()

--#nums  获取数组长度

排序算法01-直接插入排序（用C++、C#、lua实现）

1、直接插入排序

2、C#实现

3、C++实现

4、lua实现

5、新知识和疑问