- package com.itheima;
- import java.util.Arrays;
- /**
- * 1、 排序有哪几种方法?请列举。并用JAVA实现一个快速排序.
- *
- * @author snow
- *
- */
- public class Test1 {
- public static void main(String[] args) {
- int arr[] = new int[] { 10, 8, 20, 11, 19 };
- // int[] a = {2, 34, 2};// 一个数组的定义和实例化
- // System.out.println(Arrays.toString(sort2(arr)));
- System.out.println(Arrays.toString(sort4(arr, 0, arr.length - 1)));
- System.out.println(Arrays.toString(sort6(arr, arr)));
- }
- // 冒泡排序法
- public static int[] sort1(int[] arr) {
- for (int i = 0; i < arr.length; i++) {
- int temp = 0;
- for (int j = 0; j < arr.length - i - 1; j++) {
- if (arr[j] > arr[j + 1]) {
- temp = arr[j];
- arr[j] = arr[j + 1];
- arr[j + 1] = temp;
- }
- }
- }
- return arr;
- }
- // 插入排序法
- public static int[] sort2(int[] arr, int left, int right) {
- for (int i = left, j = i; i < right; j = ++i) {
- int arri = arr[i + 1];
- while (arri < arr[j]) {
- arr[j + 1] = arr[j];
- if (j-- == left) {
- break;
- }
- }
- arr[j + 1] = arri;
- }
- return arr;
- }
- // 选择排序法
- public static int[] sort3(int[] arr) {
- for (int i = 0; i < arr.length - 1; i++) {
- int j = i;
- int temp = 0;
- for (int k = i + 1; k < arr.length; k++) {
- if (arr[k] < arr[j]) {
- j = k;
- }
- }
- if (j != i) {
- temp = arr[j];
- arr[j] = arr[i];
- arr[i] = temp;
- }
- }
- return arr;
- }
- // 快速排序法
- /**
- * 快速排序思想: 1,首先找到中间的数,i初始为0递增,直到大于或等于中间的数。j初始为length-1递减,直到小于或者等于中间的数。
- * 2,交换i,j所指向的数。
- * 3,递归调用该方法。
- * @param arr
- * @param left
- * @param right
- * @return
- */
- public static int[] sort4(int[] arr, int left, int right) {
- int i = left, j = right;
- int middle, temp;
- middle = arr[(left + right) / 2];
- do {
- while ((arr[i] < middle) && (i < right)) {
- i++;
- }
- while ((arr[j] > middle) && (j > left)) {
- j--;
- }
- if (i <= j) {
- temp = arr[i];
- arr[i] = arr[j];
- arr[j] = temp;
- i++;
- j--;
- }
- } while (i <= j);
- if (left < j) {
- sort4(arr, left, j);
- }
- if (right > i)
- sort4(arr, i, right);
- return arr;
- }
- public static int[] sort5(int[] arr, int step) {
- int min;
- int temp;
- int sequence = 1;
- while (sequence < arr.length / step) {
- sequence = sequence * step + 1; // 产生到以step为步长到arr.length的最大值.
- }
- while (sequence > 0) {
- for (int i = sequence; i < arr.length; i++) {
- temp = arr[i];
- min = i;
- while (min > sequence - 1 && arr[min - sequence] > temp) {
- arr[min] = arr[min - sequence];
- min = min - sequence;
- }
- arr[min] = temp;
- }
- sequence = (sequence - 1) / step; // 递减序列关键字
- }
- return arr;
- }
-
- /**
- * 归并操作的工作原理如下:
- * 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
- * 设定两个指针,最初位置分别为两个已经排序序列的起始位置
- * 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
- * 重复步骤3直到某一指针达到序列尾
- * 将另一序列剩下的所有元素直接复制到合并序列尾
- * @param data1
- * @param data2
- * @return
- */
- public static int[] sort6(int[] data1, int[] data2) {
- int[] temp = new int[data1.length + data2.length];
- int i = 0, j = 0, iter = 0;
- for (; i < data1.length && j < data2.length;) {
- if (data1[i] <= data2[j]) {
- temp[iter] = data1[i];
- iter++;
- i++;
- } else {
- temp[iter] = data2[j];
- iter++;
- j++;
- }
- }
- for (; i < data1.length; i++, iter++) {
- temp[iter] = data1[i];
- }
- for (; j < data2.length; j++, iter++) {
- temp[iter] = data2[j];
- }
- return temp;
- }
- }
复制代码- 自己总结的
- 这里给你推荐一个好网站
- 建议:静下心。debug。思考。总结。
- http://en.wikipedia.org/wiki/Sorting_algorithm
|