Java程序辅导

Lab lecture exercises – 30 October 2015
Sorting algorithms are algorithms that leave the elements in an array unchanged, but
bring them into an order so that the array is sorted. We consider two important sorting
algorithms. The first, bubbleSort, is very easy, but also inefficient and cannot be used on
big arrays. The second, quickSort, is more complicated, but also one of the most efficient
sorting algorithms. First however, we write a method that checks whether an array is
sorted in increasing order.
1. Method for Checking the Sortedness of an array
Write a method public static boolean isSorted(double[] arr) which tests
whether a given array is sorted in increasing order. E.g., the array
a1 = {1.0, 1.1, 2.0, 2.0, 3.0} is sorted, but the array
a2 = {1.0, 1.1, 2.1, 2.0, 3.0} is not.
2. bubbleSort
bubbleSort is an algorithm for sorting arrays (e.g., of type double[]) by comparing
neighbouring elements and swapping their position if they are out of order until the
whole array is sorted. In the version we consider it starts comparing the last and the
second last elements a[size-1] and a[size-2], then compares the second last and
the third last and so on, and always swaps elements if they need to be swapped. This
means that once it reaches a[0], the smallest entry will be in the right place. It then
starts from the back again, comparing pairs of ‘neighbours’, but leaving the zeroth
entry alone (which is known to be correct). After it has reached the front again, the
second-smallest entry will be in place. It keeps making ‘passes’ over the array until
it is sorted.
In pseudo code this is:
for (int i=1; i=i; j--){
if (a[j]