三．基础排序算法
许多数据结构主要的设计目的，就是为了便于数据的有效存储、排序、查找等的处理工作。
选择排序时效率最高的(虽然三个算法遍历次数相同，但是选择排序是多次判断后赋值给或操作临时变量，最终将最大最小值赋值给或操作数据数组。而其他均在多次判断后直接赋值给或操作数据数组)。
冒泡排序算法
本质：遍历从头到最后第二个，比较下个元素，较小的到左边，
多次遍历整个列，比较相邻的数值，如果左侧的数值大于右侧数值就进行交换(将较小的交换到左边)。
长度为n的数组，需要n(n-1)/2次。操作数组n(n-1)/2次。
for(int i = a.Length-1; i >0; i--)///9,……,1
{
for(int j = 0; j < i; j++)///0,……,8;0,……,7;……;0
{
if(a[j] > a[j + 1])///9次+8次+……+1次
{
int swap = a[j + 1];
a[j + 1] = a[j];
a[j] = swap;
}
k++;
}
}
索引号遍历轨迹：
→0,1,2,3,4,5,6,7,8,9
→0,1,2,3,4,5,6,7,8
→0,1,2,3,4,5,6,7
→0,1,2,3,4,5,6
→0,1,2,3,4,5
→0,1,2,3,4
→0,1,2,3
→0,1,2
→0,1
较大的数向右移动(交换)
选择排序算法
本质：遍历从第一个到最后第二个，比较下面所有元素，找最小(大)的数放在最前(后)位
从第一个元素起比较后面的其他元素，将最小的元素放在第一个位置。再从第二个元素起重复，将后面的最小元素放在第二个位置。
长度为n的数组，需要n(n-1)/2次。操作数组n次。
for(int i = 0; i<=a.Length-1; i++)///0,……,9
{
intminIndex = 0;
for(int j = i+1; j<=a.Length-1; j++)///1,……,9;2,……,9;……;9
{
if(a[j] < a[minIndex])///9次+8次+……+1次
{
minIndex = j;
}
k++;
}
intswap = a[i];
a[i] = a[minIndex];
a[minIndex] = swap;
}
索引号遍历轨迹：
→0,1,2,3,4,5,6,7,8,9
→1,2,3,4,5,6,7,8,9
→2,3,4,5,6,7,8,9
→3,4,5,6,7,8,9
→4,5,6,7,8,9
→5,6,7,8,9
→6,7,8,9
→7,8,9
→8,9
最小的数放在最前面位置
插入排序算法
本质：遍历从第二个到最后个，比较前个元素，较小的到左边，
从第二个位置起，遍历前面的元素，将较小的交换到左边。再从第三个位置起，同样操作，直到最后一个位置。
长度为n的数组，需要n(n-1)/2次。操作数组n(n-1)/2次。
for(int i = 1; i <= a.Length - 1; i++)///1,……,9
{
inttemp = a[i];
intj = i;
while(j > 0 && a[j - 1] >= temp)///1,……,0;2,……,0;……;9,……,0;
{
a[j] = a[j - 1];
j -= 1;
}
a[j] = temp;
k += i;///9次+8次+……+1次
}
索引号遍历轨迹：
0,1←
0,1,2←
0,1,2,3←
0,1,2,3,4←
0,1,2,3,4,5←
0,1,2,3,4,5,6←
0,1,2,3,4,5,6,7←
0,1,2,3,4,5,6,7,8←
0,1,2,3,4,5,6,7,8,9←
较大的数向右移动(交换)