经典排序算法java,python实现

SOERTING ALGORITHM

排序算法java,python version1.bubbleSort（冒泡排序）java versionpython version 2.insertionSort（插入排序）java versionpython version 3.selectionSort（选择排序）java versionpython version 复杂度稳定性总结14.mergeSort（归并排序）java versionpython version 5.quickSort（快速排序）java versionpython version (java style, python style) 6.heapSort（堆排序）java versionpython version 复杂度稳定性总结2

排序算法java,python version

Talk is cheap, now show u the code.

1.bubbleSort（冒泡排序）

java version

public class BubbleSort01 { public static void bubble(double[] arr){ if (arr == null || arr.length < 2){ return; } for (int end = arr.length - 1; end > 0; end--){ for ( int i = 0; i < end; i++){ if (arr[i] > arr[i+1]){ swap(arr, i, i+1); } } } } public static void swap(double[] arr, int i, int j){ double temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } public static void main(String[] args){ double[] arr = {64, 34, 25.7, 12, -42, 11, -4.9, 90}; bubble(arr); for (double temp : arr){ System.out.print(temp + ","); } } } //-42.0,-4.9,11.0,12.0,25.7,34.0,64.0,90.0,

python version

def bubbleSort(arr): if arr == [] or len(arr) < 2: return; for e in range(len(arr)-1, 0, -1): for i in range(0, e): if arr[i] > arr[i+1]: arr[i], arr[i+1] = arr[i+1],arr[i] arr = [64, 34, 25.7, 12, -42, 11, -4.9, 90] bubbleSort(arr) print(arr) #[-42, -4.9, 11, 12, 25.7, 34, 64, 90]

2.insertionSort（插入排序）

java version

public class InserSort01 { public static void insertSort(double[] arr){ if (arr == null || arr.length < 2){ return; } for (int i = 1; i < arr.length; i++){ for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--){ swap(arr, j, j + 1); } } } public static void swap(double[] arr, int i, int j){ double temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } public static void main(String[] args){ double[] arr = {64, 34, 25.7, 12, -42, 11, -4.9, 90}; insertSort(arr); for (double temp : arr){ System.out.print(temp + ","); } } } //-42.0,-4.9,11.0,12.0,25.7,34.0,64.0,90.0,

python version

def insertSort(arr): if arr == [] or len(arr) < 2: return; for i in range(1, len(arr)-1): for j in range(i-1, -1, -1): if j >= 0 and arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] else: break arr = [64, 34, 25.7, 12, -42, 11, -4.9, 90] insertSort(arr) print(arr) #[-42, -4.9, 11, 12, 25.7, 34, 64, 90]

3.selectionSort（选择排序）

java version

package Code_01; public class SelectSort001 { public static void selectSort(double[] arr){ if (arr == null || arr.length < 2){ return; } for(int i = 0; i < arr.length -1; i++){ int minIndex = i; for (int j = i +1; j < arr.length; j++){ minIndex = arr[minIndex] < arr[j]? minIndex: j; } swap(arr, minIndex, i); } } public static void swap(double[] arr, int i, int j){ double temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } public static void main(String[] args) { double[] arr = {64, 34, 25.7, 12, -42, 11, -4.9, 90}; selectSort(arr); for (double temp : arr){ System.out.print(temp + ","); } } } //-42.0,-4.9,11.0,12.0,25.7,34.0,64.0,90.0

python version

def selectSort(arr): if arr == [] or len(arr) < 2: return for i in range(0, len(arr) - 1): minIndex = i for j in range(i+1, len(arr)): minIndex = minIndex if arr[minIndex] < arr[j] else j arr[minIndex], arr[i] = arr[i], arr[minIndex] arr = [64, 34, 25.7, 12, -42, 11, -4.9, 90] selectSort(arr) print(arr) # [-42, -4.9, 11, 12, 25.7, 34, 64, 90]

复杂度稳定性总结1

算法复杂度稳定性bubbleSortO(n^2)稳定insertionfSortO(n^2)稳定selectionSortO(n^2)不稳定

4.mergeSort（归并排序）

java version

package Code_01; public class MergeSort01 { public static void mergeSort(double[] arr){ if (arr == null || arr.length < 2){ return; } mergeSort(arr, 0, arr.length - 1); } public static void mergeSort(double[] arr, int l, int r){ if (l == r){ return; } int mid = l + ((r - l) >> 1); mergeSort(arr, l, mid); mergeSort(arr, mid + 1, r); merge(arr, l, mid, r); } public static void merge(double[] arr, int l, int m, int r) { double[] help = new double[r - l + 1]; int i = 0; int p1 = l; int p2 = m + 1; while (p1 <= m && p2 <= r) { help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++]; } while (p1 <= m) { help[i++] = arr[p1++]; } while (p2 <= r) { help[i++] = arr[p2++]; } for (i = 0; i < help.length; i++) { arr[l + i] = help[i]; } } public static void main(String[] args){ double[] arr = {64, 34, 25.7, 12, -42, 11, -4.9, 90}; mergeSort(arr); for (double temp : arr){ System.out.print(temp + ","); } } } //-42.0,-4.9,11.0,12.0,25.7,34.0,64.0,90.0,

python version

def mergeSort(arr): if arr == [] or len(arr) < 2: return mSort(arr, 0, len(arr) - 1) def mSort(arr, l, r): if l == r: return mid = l + ((r - l)>>1) mSort(arr, l, mid) mSort(arr, mid + 1, r) merge(arr, l, mid, r) def merge(arr, l, mid, r): help = [0]*(r - l +1) i = 0 p1 = l p2 = mid +1 while(p1 <= mid and p2 <= r): if arr[p1] < arr[p2]: help[i] = arr[p1] i += 1 p1 += 1 else: help[i] = arr[p2] i += 1 p2 += 1 while p1 <= mid: help[i] = arr[p1] i += 1 p1 += 1 while p2<= r: help[i] = arr[p2] i += 1 p2 += 1 for i in range(0,len(help) ): arr[l + i] = help[i] arr = [64, 34, 25.7, 12, -42, 11, -4.9, 90] mergeSort(arr) print(arr) # [-42, -4.9, 11, 12, 25.7, 34, 64, 90]

5.quickSort（快速排序）

java version

package Code_01; public class QuickSort01 { public static void quickSort(double[] arr){ if (arr == null || arr.length < 2){ return; } quickSort(arr, 0, arr.length - 1); } public static void quickSort(double[] arr, int l, int r){ if (l < r){ swap(arr, l + (int)(Math.random() * (r - l +1)), r); int[] p = partition(arr, l, r); quickSort(arr, l, p[0] - 1); quickSort(arr, p[1] + 1, r); } } public static int[] partition(double[] arr, int l, int r){ int less = l - 1; int more = r; while (l < more){ if (arr[l] < arr[r]){ swap(arr, ++less, l++); }else if (arr[l] > arr[r]){ swap(arr, --more, l); }else { l++; } } swap(arr, more, r); return new int[] {less + 1, more}; } public static void swap(double[] arr, int i, int j){ double temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } public static void main(String[] args){ double[] arr = {64, 34, 25.7, 12, -42, 11, -4.9, 90}; quickSort(arr); for (double temp : arr){ System.out.print(temp + ", "); } } } //-42.0, -4.9, 11.0, 12.0, 25.7, 34.0, 64.0, 90.0,

python version (java style, python style)

# java style def quickSort(arr): if arr == [] or len(arr) < 2: return qSort(arr, 0, len(arr) - 1) def qSort(arr, l, r): if l < r: p = partition(arr, l, r) qSort(arr, l, p[0] - 1) qSort(arr, p[1] + 1, r) def partition(arr, l, r): less = l - 1 more = r while(l < more): if arr[l] < arr[r]: less += 1 arr[l], arr[less] = arr[less], arr[l] l += 1 elif arr[l] > arr[r]: more -= 1 arr[l], arr[more] = arr[more], arr[l] else: l += 1 arr[r], arr[more] = arr[more], arr[r] return [less +1, more] arr = [64, 34, 25.7, 12, -42, 11, -4.9, 90] quickSort(arr) print(arr) # [-42, -4.9, 11, 12, 25.7, 34, 64, 90] # python style def quickSort(arr): if arr == [] or len(arr) < 2: return arr mid = arr[0] less = quickSort([i for i in arr[1:] if i < mid]) more = quickSort([j for j in arr[1:] if j >= mid]) return less + [mid] + more arr = [64, 34, 25.7, 12, -42, 11, -4.9, 90] new_arr = quickSort(arr) print(new_arr) # [-42, -4.9, 11, 12, 25.7, 34, 64, 90]

6.heapSort（堆排序）

java version

package Code_01; public class HeapSort01 { public static void heapSort(int[] arr){ if (arr == null || arr.length < 2){ return; } for (int i = 0; i < arr.length; i++){ heapInsert(arr, i); } int size = arr.length; swap(arr, 0, --size); while (size > 0){ heapify(arr, 0, size); swap(arr, 0, --size); } } public static void heapInsert(int[] arr, int index){ while (arr[index] > arr[(index - 1) / 2]){ swap(arr, index, (index -1) / 2); index = (index - 1) / 2; } } public static void heapify(int[] arr, int index, int size){ int left = index * 2 + 1; while (left < size){ int largest = left + 1 <size && arr[left + 1] > arr[left] ? left + 1 : left; largest = arr[largest] > arr[index] ? largest : index; if (largest == index){ break; } swap(arr, index, largest); index = largest; left = index * 2 + 1; } } public static void swap(int[] arr, int i, int j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } public static void main(String[] args){ int[] arr = {-3, 45, 98, 4, -67, -99, 0, 67}; heapSort(arr); for (int temp : arr) { System.out.print(temp + ", "); } } } //-99, -67, -3, 0, 4, 45, 67, 98,

python version

def heapSort(arr): if arr == [] or len(arr) < 2: return for i in range(len(arr)): heapInsert(arr, i) size = len(arr) size -= 1 arr[0], arr[size] = arr[size], arr[0] while size > 0: heapify(arr, 0, size) size -= 1 arr[size], arr[0] = arr[0], arr[size] def heapInsert(arr, index): while arr[index] > arr[int((index - 1) / 2)]: arr[index], arr[int((index - 1) / 2)] = arr[int((index - 1) / 2)], arr[index] index = int((index - 1) / 2) def heapify(arr, index, size): left = index * 2 + 1 while left < size: largest = (left + 1) if left + 1 < size and arr[left + 1] >arr[left] else left largest = index if arr[index] > arr[largest] else largest if largest == index: break arr[largest], arr[index] = arr[index], arr[largest] index = largest left = index * 2 + 1 arr = [64, 34, 25.7, 12, -42, 11, -4.9, 90] heapSort(arr) print(arr) # [-42, -4.9, 11, 12, 25.7, 34, 64, 90]

复杂度稳定性总结2

算法复杂度稳定性mergeSortO(nlogn)稳定quickSortO(nlogn)不稳定heapSortO(nlogn)不稳定

推荐：左程云算法笔记