privatestaticvoidshellSort(int[] a){ int count = 0; for (int gap = a.length /2; gap > 0; gap /= 2) { for (int i = gap; i < a.length; i++) { int index = i; int arr = a[index]; if (arr < a[index-gap]) { while (index - gap >= 0 && arr < a[index-gap]) { count ++ ; a[index] = a[index-gap]; index-=gap; } a[index] = arr; } } } System.out.println("一共:"+count+"次"); } int[] a = {4,3,5,2,1,9,8,10,7,6};
privatestaticvoidsort(int[] arr, int left, int right){ if (left < right) { int mid = (left + right) / 2; //左归并 sort(arr, left, mid); //右归并 sort(arr, mid + 1, right); //归并计算 merge(arr, left, mid, right); } }
privatestaticvoidmerge(int[] arr, int left, int mid, int right){ count ++ ; int i = left; int j = mid + 1; int[] temp = newint[right-left+1]; int t = 0;
while (i <= mid && j <= right) { if (arr[i] < arr[j]) { //左边小,将左边的数放入数组中 temp[t++] = arr[i++]; }else { //右边小,将右边的数据放入数组中 temp[t++] = arr[j++]; } }
//将剩下的数据放入数组中 while (i <= mid) { temp[t++] = arr[i++]; }
while (j <= right) { temp[t++] = arr[j++]; }
//将temp的数据放入arr中 t = 0; while (t < temp.length) { arr[left++] = temp[t++]; } } }
privatestaticvoidsort(int[] arr){ int max = arr[0]; for (int i = 0; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; } } int size = (max + "").length(); /** * size表示循环的次数,根据最大数的位数决定,n表示当前应该取哪一位数,n为1的时候表示取个位 * n为10表示取百位,以此类推,每次遍历都创建一个length*10的桶,保证数据不会出错 * 存的时候是按照行列存储的,但取得时候按照列行取(按照人的思维) */ for (int k = 0, n = 1; k < size; k++, n *= 10) { //创建一个二维数组用来表示放置的桶 int[][] bucket = newint[arr.length][10]; for (int i = 0; i < arr.length; i++) { int temp = arr[i]; int gewei = temp / n % 10; bucket[i][gewei] = temp; } int t = 0; for (int i = 0; i < 10; i++){ for (int j = 0; j < arr.length; j++){ if (bucket[j][i] != 0) { arr[t++] = bucket[j][i]; } } } System.out.println(Arrays.toString(arr)); } }