[SOLVED] 程序代写代做代考 Java algorithm Untitled

Untitled

import java.util.*;
public class Sorts {

//swap method to be used in all sorting algorithms
private static void swap(int[] arr,int num1, int num2) {
int temp = arr[num1];
arr[num1] = arr[num2];
arr[num2] = temp;
}

//Adapted from Professor Langsam’s notes.

//Plan: Pass through the array, and swap any pair of elements that is out of
order.

public static void bubbleSort(int[] arr) {
boolean isSorted = false;//we will keep track of whether or not the array is
sorted as we go through. At first, we assume that the array is unsorted.
for(int pass = 0; pass < arr.length-1 && !isSorted; pass++) // we only have to make n-1 passes since if the first n-1 numbers are sorted, the array is sorted.{isSorted = true; //we make the hopeful assumption that the array will be sorted.for(int i = 0 ; i arr[i+1]) {
isSorted = false;//if a swap is performed, we know that
the array is still unsorted.
swap(arr, i, i+1);

}
}
}
}

//Adapted from McConnell (2008)
//Plan: On any arbitrary pass i through the for loop, all of the elements
arr[0..i-1] is in sorted order.
//Repeatedly copy elements over one by one until you find where the new
element, arr[i] should go.

public static void insertionSort(int[] arr) {
for(int i=1; i =0 && arr[location] > newElement) { //while location
is still in bounds, and newElement is still out of order
arr[location+1] = arr[location];// copy the elements over
one by one to make space for “newElement”
location–;
}
arr[location+1] = newElement;
}
}

//findMinimumIndex() is a subroutine to selectionSort. It finds the index of
minimum element in the array from arr[start..end-1].

private static int findMinimumIndex (int[] arr, int start, int end) {

int minIndex = start;
int minValue = arr[start];

for(int i=start+1; i =pivot.
//This function returns the index of the pivot.

//This version of partition() is adapted from CLRS(2009), but there are other
ways of doing this.

private static int partition(int[] arr, int start, int end) {

int pivot = arr[start];

int boundaryIndex = start; //on an arbitrary iteration of this loop, all
elements in arr[start..boundaryIndex] are <=pivot//and all elements in arr[boundaryIndex+1..newElement-1] are >=pivot.

for(int newElementIndex = start+1; newElementIndex =pivot, we are happy, since we can just move
the boundary of >= by one element and do no extra work.
//Now, if arr[newElementIndex] <=pivot, we must swap the new element we encounter with the element on the boundary, thus maintaining the invariant.if(arr[newElementIndex] <= pivot) {boundaryIndex++;swap(arr, boundaryIndex, newElementIndex);}}swap(arr, boundaryIndex, start);return boundaryIndex;}//Quicksort works by partitioning the array into 2 subarrays around a pivot.//if the pivot is at index x, then all numbers in arr[0..x-1] <=x//and all elements in arr[x+1..n-1] >=x.
//Because of this property, if we recursively sort each subarray, we will get an
overall
//sorted array.

private static void quicksort(int[] arr, int start, int end) {

if((end-start)<=1)return;int pivotIndex = partition(arr, start, end);quicksort(arr, start, pivotIndex);quicksort(arr, pivotIndex+1, end);}public static void quicksort(int[] arr) {quicksort(arr, 0, arr.length);}public static void shuffle(int[] arr) {Random r = new Random();for(int i=0; i