int[] attr = {5,6,2,7,4,13,3,20,14,15,10,11,6,9,8,16};
冒泡排序
大的下沉，小的上浮。
每次循环都从头(0)开始比较到(attr.length-循环次数)位置，每次比较相邻两个元素，前一个元素大于后一个元素，则两个元素交换值。
public void bubblingSort(int[] attr) {
for (int i = attr.length - 1; i >= 0; i--) {
for (int j = 0; j < i; j++) {
if (attr[j] > attr[j + 1]) {
int temp = attr[j];
attr[j] = attr[j + 1];
attr[j + 1] = temp;
}
}
}
}
鸡尾酒排序(升级版冒泡排序)
大的下沉，小的上浮。
奇次循环从头开始两两比较大的下沉，偶次循环从末尾开始两两比较小的上浮。
public void flipSort(int[] attr) {
int start = 0;
int end = attr.length - 1;
int temp;
while (start < end) {
for (int i = start; i < end; i++) {
if (attr[i] > attr[i + 1]) {
temp = attr[i];
attr[i] = attr[i + 1];
attr[i + 1] = temp;
}
}
end--;
for (int j = end; j > start; j--) {
if (attr[j] < attr[j - 1]) {
temp = attr[j - 1];
attr[j - 1] = attr[j];
attr[j] = temp;
}
}
start++;
}
}
选择排序
每次从无序序列中选择最大（最小）放到有序序列的末尾。
每次循环都从头(0)开始比较到(attr.length-循环次数)位置，比较每次循环的最后一个元素和前面其他元素，如果有比最后一个元素大的值就和其交换。
public void selectSort(int[] attr) {
for (int i = attr.length - 1; i >= 0; i--) {
for (int j = 0; j < i; j++) {
if (attr[j] > attr[i]) {
int temp = attr[j];
attr[j] = attr[i];
attr[i] = temp;
}
}
}
}
插入排序
从无序序列中取出一个元素放入到有序列相应的位置中。
默认无序序列第一个为有序序列，然后从无序序列第二个开始取元素k，从有序序列末尾元素开始依次和元素k比较，比k大则后移一位，直到不比k大时，将k插入到空位。重复执行以上循环到无序序列每个元素都插入到了有序序列中。
public void insertSort(int[] attr) {
for (int i = 1; i < attr.length; i++) {
int get = attr[i];
int j = i - 1;
while (j >= 0 && attr[j] > get) {
attr[j + 1] = attr[j];
j--;
}
attr[j + 1] = get;
}
}
二分法插入排序
从无序序列中取出一个元素放入到有序列相应的位置中。
默认无序序列第一个为有序序列，然后从无序序列第二个开始取元素k，然后取出有序序列中间位置的元素和元素k比较，比k大则取有序序列头到序列中间段重复上述比较，比k小则取有序序列中间位置到序列末尾段重复上述比较，直到取出的序列段只有一个元素z并确定k元素和z位置关系，再然后将k元素插入位置后的元素全部后移，最后将k插入到空位。重复执行以上循环到无序序列每个元素都插入到了有序序列中。
public void dichotomySort(int[] attr){
for (int i = 1; i < attr.length; i++) {
int temp = attr[i];
int l = 0;
int h = i - 1;
int min = -1;
while (l <= h){
min = (h + l) /2;
if (attr[min] > temp){
h = min - 1;
} else {
l = min + 1;
}
}
for (int j = i - 1; j >= l; j--) {
attr[j+1] = attr[j];
}
attr[l] = temp;
}
}
快速排序
选取一个参考值key，然后将比key大的放到key之后，比key小的放到key之前。再然后以key的位置分两段进行之前的操作，直到无法再分为止。
每次循环前选取一个key(通常选择序列中第一个)作为参考，然后从序列末尾（指针j）开始找到第一个比key小的值与key互换位置，再然后从序列头（指针i）开始找到第一个比序列大的值与key互换位置，继续以上互换直到i大于等于j结束本次循环，最后以key的位置为界将序列分为前后两段分别进行上述循环，直到序列无法继续分段为止（即开始指针大于等于结束指针）。
public void quickSort(int start, int end, int[] attr) {
if (start >= end) {
return;
}
int key = attr[start];
int i = start;
int j = end;
while (i < j) {
while (i < j && attr[j] >= key) {
j--;
}
attr[i] = attr[j];
while (i < j && attr[i] <= key) {
i++;
}
attr[j] = attr[i];
}
attr[i] = key;
quickSort(start, i - 1, attr);
quickSort(i + 1, end, attr);
}
