例:70 73 69 23 93 18 11 68
i j
快速排序
1. 用最后一个数和这组数(从头)开始比较大小,
若这个数小于数组比较的这个数,则交换这两个数的位置
即j与i比较大小;
for (int i=0;i<10;i++)
for(int j=9;j>=0;j--)
排序1:68 73 69 23 93 18 11 70
i i+1 j
结 果:68 70 69 23 93 18 11 73
O(3)
排序2:68 70 69 23 93 18 11 73
i i+1 i+2 i+3 i+4 j
结果: 68 70 69 23 73 18 11 93
O(6)
排序3:68 70 69 23 73 18 11 93 //确定93为最大的数
i i+1 i+2 i+3 i+4 i+5 i+6 j
//从这一步可知,下一个数由j+1与前数组注意比较
结果: 68 70 69 23 73 18 11 93
// 意味着开始j的第二重循环
O(7)
排序4:68 70 69 23 73 18 11 93
i j-1 j
结果: 11 70 69 23 73 18 68 93
O(2)
排序5:11 70 69 23 73 18 68 93
i i+1 j-1 j
结果: 11 68 69 23 73 18 70 93
O(3)
排序6:11 68 69 23 73 18 70 93
i i+1 i+2 i+3 i+4 j-1 j
结果: 11 68 69 23 70 18 73 93
O(6)
排序7: 11 68 69 23 70 18 73 93
i i+1 j-2 j-1 j
结果: 11 18 69 23 70 68 73 93
O(3)
排序8:11 18 69 23 70 68 73 93
i i+1 i+2 j-2 j-1 j
结果: 11 18 68 23 70 69 73 93
O(4)
排序9: 11 18 68 23 70 69 73 93
i i+1 i+2 i+3 i+4 j-2 j-1 j
结果: 11 18 68 23 69 70 73 93
O(6)
排序10:11 18 68 23 69 70 73 93
i i+1 i+2 i+3 j-3 j-2 j-1 j
结果: 11 18 68 23 69 70 73 93
O(4)
排序11:11 18 68 23 69 70 73 93
i i+1 i+2 j-4 j-3 j-2 j-1 j
结果: 11 18 23 68 69 70 73 93
O(4)
预计时间复杂度:O(n)=O(48)
最大是多少?