/** * 冒泡排序 * @param arr * @return arr */ publicstaticint[] BubbleSort(int[] arr) { for (int i = 1; i < arr.length; i++) { // Set a flag, if true, that means the loop has not been swapped, // that is, the sequence has been ordered, the sorting has been completed. boolean flag = true; for (int j = 0; j < arr.length - i; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; // Change flag flag = false; } } if (flag) { break; } } return arr; }
1 2 3 4 5 6 7 8 9 10
defBubbleSort(arr): for i in range(len(arr)): is_sorted = True for j in range(len(arr)-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] is_sorted = False if is_sorted: break return arr
/** * 选择排序 * @param arr * @return arr */ publicstaticint[] SelectionSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int minIndex = i; for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } if (minIndex != i) { int tmp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = tmp; } } return arr; }
1 2 3 4 5 6 7 8 9 10
defSelectionSort(arr): for i in range(len(arr)-1): # 记录最小值的索引 minIndex = i for j in range(i+1, len(arr)): if arr[j] < arr[minIndex]: minIndex = j if minIndex != i: arr[i], arr[minIndex] = arr[minIndex], arr[i] return arr
/** * 插入排序 * @param arr * @return arr */ publicstaticint[] InsertionSort(int[] arr) { for (int i = 1; i < arr.length; i++) { int preIndex = i - 1; int current = arr[i]; while (preIndex >= 0 && current < arr[preIndex]) { arr[preIndex + 1] = arr[preIndex]; preIndex -= 1; } arr[preIndex + 1] = current; } return arr; }
1 2 3 4 5 6 7 8 9
defInsertionSort(arr): for i in range(1, len(arr)): preIndex = i-1 current = arr[i] while preIndex >= 0and current < arr[preIndex]: arr[preIndex+1] = arr[preIndex] preIndex -= 1 arr[preIndex+1] = current return arr
/** * 希尔排序 * * @param arr * @return arr */ publicstaticint[] ShellSort(int[] arr) { int n = arr.length; int gap = n / 2; while (gap > 0) { for (int i = gap; i < n; i++) { int current = arr[i]; int preIndex = i - gap; // Insertion sort while (preIndex >= 0 && arr[preIndex] > current) { arr[preIndex + gap] = arr[preIndex]; preIndex -= gap; } arr[preIndex + gap] = current;
} gap /= 2; } return arr; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
defShellSort(arr): n = len(arr) # 初始步长 gap = n // 2 while gap > 0: for i in range(gap, n): # 根据步长进行插入排序 current = arr[i] preIndex = i - gap # 插入排序 while preIndex >= 0and arr[preIndex] > current: arr[preIndex+gap] = arr[preIndex] preIndex -= gap arr[preIndex+gap] = current # 得到新的步长 gap = gap // 2 return arr
归并排序(Merge Sort)
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。
/** * Swap the two elements of an array * @param array * @param i * @param j */ privatestaticvoidswap(int[] arr, int i, int j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }
/** * Partition function * @param arr * @param left * @param right * @return small_idx */ privatestaticintPartition(int[] arr, int left, int right){ if (left == right) { return left; } // random pivot int pivot = (int) (left + Math.random() * (right - left + 1)); swap(arr, pivot, right); int small_idx = left; for (int i = small_idx; i < right; i++) { if (arr[i] < arr[right]) { swap(arr, i, small_idx); small_idx++; } } swap(arr, small_idx, right); return small_idx; }
/** * Quick sort function * @param arr * @param left * @param right * @return arr */ publicstaticint[] QuickSort(int[] arr, int left, int right) { if (left < right) { int pivotIndex = Partition(arr, left, right); sort(arr, left, pivotIndex - 1); sort(arr, pivotIndex + 1, right); } return arr; }
defQuickSort(arr, left=None, right=None): left = 0if left == Noneelse left right = len(arr)-1if right == Noneelse right if left < right: pivotIndex = Partition(arr, left, right) QuickSort(arr, left, pivotIndex-1) QuickSort(arr, pivotIndex+1, right) return arr
defPartition(arr, left, right): if left == right: return left # 随机pivot swap(arr, random.randint(left, right), right) pivot = right small_idx = left for i in range(small_idx, pivot): if arr[i] < arr[pivot]: swap(arr, i, small_idx) small_idx += 1 swap(arr, small_idx, pivot) return small_idx
defswap(arr, i, j): arr[i], arr[j] = arr[j], arr[i]
// Global variable that records the length of an array; staticint heapLen;
/** * Swap the two elements of an array * @param arr * @param i * @param j */ privatestaticvoidswap(int[] arr, int i, int j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }
/** * Build Max Heap * @param arr */ privatestaticvoidbuildMaxHeap(int[] arr){ for (int i = arr.length / 2 - 1; i >= 0; i--) { heapify(arr, i); } }
/** * Adjust it to the maximum heap * @param arr * @param i */ privatestaticvoidheapify(int[] arr, int i){ int left = 2 * i + 1; int right = 2 * i + 2; int largest = i; if (right < heapLen && arr[right] > arr[largest]) { largest = right; } if (left < heapLen && arr[left] > arr[largest]) { largest = left; } if (largest != i) { swap(arr, largest, i); heapify(arr, largest); } }
/** * Heap Sort * @param arr * @return */ publicstaticint[] HeapSort(int[] arr) { // index at the end of the heap heapLen = arr.length; // build MaxHeap buildMaxHeap(arr); for (int i = arr.length - 1; i > 0; i--) { // Move the top of the heap to the tail of the heap in turn swap(arr, 0, i); heapLen -= 1; heapify(arr, 0); } return arr; }
defHeapSort(arr): global heapLen # 用于标记堆尾部的索引 heapLen = len(arr) # 构建最大堆 buildMaxHeap(arr) for i in range(len(arr)-1, 0, -1): # 依次将堆顶移至堆尾 swap(arr, 0, i) heapLen -= 1 heapify(arr, 0) return arr
defbuildMaxHeap(arr): for i in range(len(arr)//2-1, -1, -1): heapify(arr, i)
defheapify(arr, i): left = 2*i + 1 right = 2*i + 2 largest = i if right < heapLen and arr[right] > arr[largest]: largest = right if left < heapLen and arr[left] > arr[largest]: largest = left if largest != i: swap(arr, largest, i) heapify(arr, largest)
defswap(arr, i, j): arr[i], arr[j] = arr[j], arr[i]
defCountingSort(arr): if arr.size < 2: return arr minValue, maxValue = getMinAndMax(arr) countArr = [0]*(maxValue-minValue+1) resultArr = [0]*len(arr) for i in range(len(arr)): countArr[arr[i]-minValue] += 1 for i in range(1, len(countArr)): countArr[i] += countArr[i-1] for i in range(len(arr)-1, -1, -1): idx = countArr[arr[i]-minValue]-1 resultArr[idx] = arr[i] countArr[arr[i]-minValue] -= 1 return resultArr
defgetMinAndMax(arr): maxValue = arr[0] minValue = arr[0] for i in range(len(arr)): if arr[i] > maxValue: maxValue = arr[i] elif arr[i] < minValue: minValue = arr[i] return minValue, maxValue
/** * Gets the maximum and minimum values in the array * @param arr * @return */ privatestaticint[] getMinAndMax(List<Integer> arr) { int maxValue = arr.get(0); int minValue = arr.get(0); for (int i : arr) { if (i > maxValue) { maxValue = i; } elseif (i < minValue) { minValue = i; } } returnnewint[] { minValue, maxValue }; }
/** * Bucket Sort * @param arr * @return */ publicstatic List<Integer> BucketSort(List<Integer> arr, int bucket_size){ if (arr.size() < 2 || bucket_size == 0) { return arr; } int[] extremum = getMinAndMax(arr); int minValue = extremum[0]; int maxValue = extremum[1]; int bucket_cnt = (maxValue - minValue) / bucket_size + 1; List<List<Integer>> buckets = new ArrayList<>(); for (int i = 0; i < bucket_cnt; i++) { buckets.add(new ArrayList<Integer>()); } for (int element : arr) { int idx = (element - minValue) / bucket_size; buckets.get(idx).add(element); } for (int i = 0; i < buckets.size(); i++) { if (buckets.get(i).size() > 1) { buckets.set(i, sort(buckets.get(i), bucket_size / 2)); } } ArrayList<Integer> result = new ArrayList<>(); for (List<Integer> bucket : buckets) { for (int element : bucket) { result.add(element); } } return result; }
defBucketSort(arr, bucket_size): if len(arr) < 2or bucket_size == 0: return arr minValue, maxValue = getMinAndMax(arr) bucket_cnt = (maxValue-minValue)//bucket_size+1 bucket = [[] for i in range(bucket_cnt)] for i in range(len(arr)): idx = (arr[i]-minValue) // bucket_size bucket[idx].append(arr[i]) for i in range(len(bucket)): if len(bucket[i]) > 1: # 递归使用桶排序,也可使用其它排序算法 bucket[i] = BucketSort(bucket[i], bucket_size//2) result = [] for i in range(len(bucket)): for j in range(len(bucket[i])): result.append(bucket[i][j]) return result
defgetMinAndMax(arr): maxValue = arr[0] minValue = arr[0] for i in range(len(arr)): if arr[i] > maxValue: maxValue = arr[i] elif arr[i] < minValue: minValue = arr[i] return minValue, maxValue
defRadixSort(arr): if len(arr) < 2: return arr maxValue = arr[0] N = 1 for i in range(len(arr)): if arr[i] > maxValue: maxValue = arr[i] while maxValue // 10 != 0: maxValue = maxValue//10 N += 1 for n in range(N): radix = [[] for i in range(10)] for i in range(len(arr)): idx = arr[i]//(10**n) % 10 radix[idx].append(arr[i]) idx = 0 for j in range(len(radix)): for k in range(len(radix[j])): arr[idx] = radix[j][k] idx += 1 return arr