/** * bubble_sort - ascendly bubble sort the array * * @param array the array to be sorted * @param length the length of the array */ externvoidbubble_sort(intarray[], int length) { int i, j; for (i = length; i > 0; i--){ for (j = 0; j < i-1; j++){ if (array[j] > array[j+1]) swap(&array[j], &array[j+1]); } } }
/** * selection_sort - ascendly selection sort the array * * @param array the array to be sorted * @param length the length of the array * */ externvoidselection_sort(intarray[], int length) { int i, j, min; for (i = 0; i < length; i++) { min = i; for (j = i; j < length; j++) { /* search for the minimum value */ if (array[min] > array[j]) { min = j; } } if (min != i) { /* swap array[j] and min */ swap(&array[i], &array[min]); } } return; }
/** * insertion_sort - ascendly insertion sort the array * @param array the array to be sorted * @param length the length of the array * * Sorting the array ascendly by using the insertion sort algorithms. * */ extern void insertion_sort(int array[], int length) { int i, j, key; for (i = 1; i < length; j++){ key = array[i]; for (j = i - 1; j >= 0 && array[j] > key; j--){ array[j+1] = array[j]; } array[j+1] = key; } return; }
/** * shell_sort - ascendly shell sort the array * @param array the array to be sorted * @param length the length of the array * * * Sorting the array ascendly by using the shell sort algorithms. * */ voidshell_sort(intarray[], int length) { int gap, i, j, key; for (gap = length/2; gap > 0; gap /= 2) for (i = gap; i < length; i++) for (j=i-gap; j>=0 && array[j]>array[j+gap]; j-=gap) { // swap the two elements key = array[j]; array[j] = array[j+gap]; array[j+gap] = key; } return; }
性质
步长的选择
步长的选择是希尔排序的重要部分。只要最终步长为1(此时为插入排序)任何步长串行都可以工作。
Donald Shell 最初建议步长选择为 \(\frac{n}{2}\) 并且对步长取半直到步长达到 1。虽然这样取可以比 \(O(n^2)\) 类的算法(插入排序)更好,但这样仍然有减少平均时间和最差时间的余地。
/** * merge - merge array * @param array the array to be merge * @param start the start of the array * @param mid the end of the left array * @param end the end of the whole array * * A key subroutine of merge sort. * */ staticvoidmerge(intarray[], int start, int mid, int end) { // Logically divide the array into two and treat them respectively int n1 = mid - start + 1; int n2 = end - mid; int left[n1], right[n2]; int i, j, k; for (i = 0; i < n1; i++) // left holds array[start...mid] left[i] = array[start + i]; for (j = 0; j < n2; j++) // right holds array[mid+1..end] right[j] = array[mid + 1 + j]; i = j = 0; k = start; while (i < n1 && j < n2){ if (left[i] < right[j]) array[k++] = left[i++]; else array[k++] = right[j++]; } // append the rest to the array while (i < n1) // left[] is not exhausted array[k++] = left[i++]; while (j < n2) array[k++] = right[j++]; return; }
/** * msort - ascendly merge sort the array * @param array the array to be sorted * @param start the start of the array * @param end the end of the array * * Sorting the array ascendly by using the merge sort algorithms. * The core of merge sort. * */ staticvoidmsort(intarray[], int start, int end) { int mid; if (start < end){ mid = (start + end) / 2; msort(array, start, mid); msort(array, mid + 1, end); merge(array, start, mid, end); } return; }
/** * merge_sort - ascendly merge sort the array * @param array the array to be sorted * @param length the length of the array * * The interface of merge sort. * @returns 0 after sorting. * */ externvoidmerge_sort(intarray[], int length) { msort(array, 0, length-1); return; }
/** * sway - swap two integers * * @param a the first integer * @param b the second integer * */ staticvoidswap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; return; }
/** * partition - divide the array into two parts by using a pivot * @param array the array to be divided * @param start the start of the array * @param end the end of the array * * * A key subroutine of quick sort. * */ staticintpartition(intarray[], int start, int end) { int pivot = array[end]; int mid = start; int i; for (i = start; i < end; i++) { if(array[i] <= pivot){ swap(&array[i], &array[mid]); mid++; } } swap(&array[end], &array[mid]); return mid; }
/** * msort - ascendly quick sort the array * @param array the array to be sorted * @param start the start of the array * @param end the end of the array * * Sorting the array ascendly by using the quick sort algorithms. * The core of quick sort. * */ staticintq_sort(intarray[], int start, int end) { int mid; if (end > start) { mid = partition(array, start, end); q_sort(array, start, mid-1); q_sort(array, mid+1, end); } }
/** * quick_sort - ascendly quick sort the array * @param array the array to be sorted * @param length the length of the array * * The interface of quick sort. * */ externvoidquick_sort(intarray[], int length) { q_sort(array, 0, length-1); return; }