排序
2020-01-09 本文已影响0人
caoww
前沿
假如我想买一件衣服，我想在淘宝上去搜索，搜索有发现有很多，该如何去选择。其实我就想买一件便宜点，衣服质量还可以的，想找信誉好的商家，如何做？
网上搜索一下该如何做，万能的网络给我出了个注意，可以通过排序，可以按照信用、价格等进行排序之后，优先选择合适的放在最前面
此时就需要引入需要学习的东西---排序
排序的概念
- 排序是将一批无序的记录（数据）重新排列成按关键字有序的记录序列的过程。
- 排序的稳定性
- 内排序和外排序
排序的分类：
- 冒泡排序
- 选择排序
- 直接插入排序
- 希尔排序
- 堆排序排序
- 归并排序
- 快速排序
冒泡排序
public static void bubbleSort(int []arr) {
for(int i =1;i<arr.length;i++) {
for(int j=0;j<arr.length-i;j++) {
if(arr[j]>arr[j+1]) {
int temp = arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
选择排序
public static void selectionSort(int[] arr){
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}
if (min != i) {
int tmp = arr[min];
arr[min] = arr[i];
arr[i] = tmp;
}
}
}
直接插入排序
public class InsertSort{
public void insertSort(int[] array){
for(int i=1;i<array.length;i++)//第0位独自作为有序数列，从第1位开始向后遍历
{
if(array[i]<array[i-1])//0~i-1位为有序，若第i位小于i-1位，继续寻位并插入，否则认为0~i位也是有序的，忽略此次循环，相当于continue
{
int temp=array[i];//保存第i位的值
int j = i - 1;
while(j>=0 && temp<array[j])//从第i-1位向前遍历并移位，直至找到小于第i位值停止
{
array[j+1]=array[j];
j--;
}
array[j+1]=temp;//插入第i位的值
}
}
}
public static void printArray(int[] array) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]);
if (i != array.length - 1) {
System.out.print(",");
}
}
}
}
希尔排序
- code
public static void main(String[] args){
int[] array={49,38,65,97,76,13,27,49,78,34,12,64,1};
System.out.println("排序之前：");
for(int i=0;i<array.length;i++){
System.out.print(array[i]+" ");
}
//希尔排序
int gap = array.length;
while (true) {
gap /= 2; //增量每次减半
for (int i = 0; i < gap; i++) {
for (int j = i + gap; j < array.length; j += gap) {//这个循环里其实就是一个插入排序
int temp = array[j];
int k = j - gap;
while (k >= 0 && array[k] > temp) {
array[k + gap] = array[k];
k -= gap;
}
array[k + gap] = temp;
}
}
if (gap == 1)
break;
}
System.out.println();
System.out.println("排序之后：");
for(int i=0;i<array.length;i++){
System.out.print(array[i]+" ");
}
}
堆排序排序
/**
* 选择排序-堆排序
* @param array 待排序数组
* @return 已排序数组
*/
public static int[] heapSort(int[] array) {
//这里元素的索引是从0开始的,所以最后一个非叶子结点array.length/2 - 1
for (int i = array.length / 2 - 1; i >= 0; i--) {
adjustHeap(array, i, array.length); //调整堆
}
// 上述逻辑，建堆结束
// 下面，开始排序逻辑
for (int j = array.length - 1; j > 0; j--) {
// 元素交换,作用是去掉大顶堆
// 把大顶堆的根元素，放到数组的最后；换句话说，就是每一次的堆调整之后，都会有一个元素到达自己的最终位置
swap(array, 0, j);
// 元素交换之后，毫无疑问，最后一个元素无需再考虑排序问题了。
// 接下来我们需要排序的，就是已经去掉了部分元素的堆了，这也是为什么此方法放在循环里的原因
// 而这里，实质上是自上而下，自左向右进行调整的
adjustHeap(array, 0, j);
}
return array;
}
/**
* 整个堆排序最关键的地方
* @param array 待组堆
* @param i 起始结点
* @param length 堆的长度
*/
public static void adjustHeap(int[] array, int i, int length) {
// 先把当前元素取出来，因为当前元素可能要一直移动
int temp = array[i];
for (int k = 2 * i + 1; k < length; k = 2 * k + 1) { //2*i+1为左子树i的左子树(因为i是从0开始的),2*k+1为k的左子树
// 让k先指向子节点中最大的节点
if (k + 1 < length && array[k] < array[k + 1]) { //如果有右子树,并且右子树大于左子树
k++;
}
//如果发现结点(左右子结点)大于根结点，则进行值的交换
if (array[k] > temp) {
swap(array, i, k);
// 如果子节点更换了，那么，以子节点为根的子树会受到影响,所以，循环对子节点所在的树继续进行判断
i = k;
} else { //不用交换，直接终止循环
break;
}
}
}
/**
* 交换元素
* @param arr
* @param a 元素的下标
* @param b 元素的下标
*/
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
归并排序
public class MergeSort {
public static int[] mergeSort(int[] nums, int l, int h) {
if (l == h)
return new int[] { nums[l] };
int mid = l + (h - l) / 2;
int[] leftArr = mergeSort(nums, l, mid); //左有序数组
int[] rightArr = mergeSort(nums, mid + 1, h); //右有序数组
int[] newNum = new int[leftArr.length + rightArr.length]; //新有序数组
int m = 0, i = 0, j = 0;
while (i < leftArr.length && j < rightArr.length) {
newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
}
while (i < leftArr.length)
newNum[m++] = leftArr[i++];
while (j < rightArr.length)
newNum[m++] = rightArr[j++];
return newNum;
}
public static void main(String[] args) {
int[] nums = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 10 };
int[] newNums = mergeSort(nums, 0, nums.length - 1);
for (int x : newNums) {
System.out.println(x);
}
}
}
快速排序
public static int[] qsort(int arr[], int start, int end) {
int pivot = arr[start];
int i = start;
int j = end;
while (i < j) {
while ((i < j) && (arr[j] > pivot)) {
j--;
}
while ((i < j) && (arr[i] < pivot)) {
i++;
}
if ((arr[i] == arr[j]) && (i < j)) {
i++;
} else {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
if (i - 1 > start) arr = qsort(arr, start, i - 1);
if (j + 1 < end) arr = qsort(arr, j + 1, end);
return (arr);
}
public static void main(String[] args) {
int arr[] = new int[]{3, 3, 3, 7, 9, 122344, 4656, 34, 34, 4656, 5, 6, 7, 8, 9, 343, 57765, 23, 12321};
int len = arr.length - 1;
arr = qsort(arr, 0, len);
for (int i : arr) {
System.out.print(i + "\t");
}
}
/*//////////////////////////方式二////////////////////////////////*/
更高效点的代码：(TextendsComparable和SortUtil都是自己封装的类，里面重写和实现了compareTo和swap方法)
public <TextendsComparable<?superT>>
T[] quickSort(T[] targetArr, int start, int end) {
inti = start + 1, j = end;
T key = targetArr[start];
SortUtil<T> sUtil = new SortUtil<T>();
if (start == end) return (targetArr);
/*从i++和j--两个方向搜索不满足条件的值并交换
*
*条件为：i++方向小于key，j--方向大于key
*/
while (true) {
while (targetArr[j].compareTo(key) > 0) j--;
while (targetArr[i].compareTo(key) < 0 && i < j) i++;
if (i >= j) break;
sUtil.swap(targetArr, i, j);
if (targetArr[i] == key) {
j--;
} else {
i++;
}
}
/*关键数据放到‘中间’*/
sUtil.swap(targetArr, start, j);
if (start < i - 1) {
this.quickSort(targetArr, start, i - 1);
}
if (j + 1 < end) {
this.quickSort(targetArr, j + 1, end);
}
returntargetArr;
}
/*//////////////方式三：减少交换次数，提高效率/////////////////////*/
private<TextendsComparable<?superT>>
voidquickSort(T[] targetArr, intstart, intend) {
inti = start, j = end;
Tkey = targetArr[start];
while (i < j) {
/*按j--方向遍历目标数组，直到比key小的值为止*/
while (j > i && targetArr[j].compareTo(key) >= 0) {
j--;
}
if (i < j) {
/*targetArr[i]已经保存在key中，可将后面的数填入*/
targetArr[i] = targetArr[j];
i++;
}
/*按i++方向遍历目标数组，直到比key大的值为止*/
while (i < j && targetArr[i].compareTo(key) <= 0)
/*此处一定要小于等于零，假设数组之内有一亿个1，0交替出现的话，而key的值又恰巧是1的话，那么这个小于等于的作用就会使下面的if语句少执行一亿次。*/ {
i++;
}
if (i < j) {
/*targetArr[j]已保存在targetArr[i]中，可将前面的值填入*/
targetArr[j] = targetArr[i];
j--;
}
}
/*此时i==j*/
targetArr[i] = key;//应加判断
/*递归调用，把key前面的完成排序*/
this.quickSort(targetArr, start, i - 1);
/*递归调用，把key后面的完成排序*/
this.quickSort(targetArr, j + 1, end);
//两个递归应加判断
}
