冒泡排序和快速排序
2019-04-15 本文已影响0人
龙龙zzl
1.冒泡排序
public void maoPao() {
int list[] = {9,8,7,1,2,3,4,5,6};
int size = list.length;
int temp = 0;
boolean isChange = false; //判断无序区是否有变换位置
for (int i = 0; i<size - 1; i++) {
isChange = false;
for (int j = 0; j<size - 1 - i; j++) {
if (list[j] > list[j + 1]) {
temp = list[j + 1];
list[j + 1] = list[j];
list[j] = temp;
isChange = true;
}
}
//打印每趟的数组内容
Log.e("taggggg", Arrays.toString(list));
if (!isChange)
break; //如果没有变的话,说明前面的已经排好序了
}
//排序好的最终结果打印
Log.e("taggggg", Arrays.toString(list));
}
2.快速排序
1.取一个元素p(第一个元素),使元素p归位
2.列表被p分成俩部分,左边都比p小,右边都比p大
3.递归排序完成
//调用
int list[] = {5,7,4,6,3,1,2,9,8};
quick_sort(list, 0, list.length - 1);
//快速排序实现
public void quick_sort(int[] list, int left, int right) {
if (left < right) { //至少俩个元素
int mid = partition(list, left, right);
quick_sort(list, left, mid - 1);
quick_sort(list, mid + 1, right);
}
}
public int partition(int[] list, int left, int right) {
int temp = list[left];
while (left < right) {
while (left < right && list[right] >= temp) //从右边找比temp小的数
right -= 1;//往左走一步
list[left] = list[right]; //把右边的值放到左边的空位上,因为是拿走左边的值进行比较的,所以左边空位
while (left < right && list[left] <= temp) //同理
left += 1;
list[right] = list[left];//把左边的值写到右边空位上
}
list[left] = temp; //把temp归位
return left;
}