[关闭]
@bintou 2018-10-03T01:54:10.000000Z 字数 3122 阅读 808

CSI第七章查找与排序

CSI 源代码


  1. #include <stdio.h>
  2. // A recursive binary search function. It returns location of x in
  3. // given array arr[l..r] is present, otherwise -1
  4. int binarySearch(int arr[], int l, int r, int x)
  5. {
  6. if (r >= l)
  7. {
  8. int mid = l + (r - l)/2;
  9. // If the element is present at the middle itself
  10. if (arr[mid] == x) return mid;
  11. // If element is smaller than mid, then it can only be present
  12. // in left subarray
  13. if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);
  14. // Else the element can only be present in right subarray
  15. return binarySearch(arr, mid+1, r, x);
  16. }
  17. // We reach here when element is not present in array
  18. return -1;
  19. }
  20. int ite_binarySearch(int* array, int size, int key)
  21. {
  22. int left = 0, right = size, mid = -1;
  23. while(left <= right)
  24. {
  25. mid = (left + right)/2;
  26. if(array[mid] == key)
  27. return mid;
  28. if(array[mid] < key)
  29. left = mid + 1;
  30. else
  31. right = mid - 1;
  32. }
  33. return -1;
  34. }
  35. int main(void)
  36. {
  37. int arr[] = {2, 3, 4, 10, 40};
  38. int n = sizeof(arr)/ sizeof(arr[0]);
  39. int x = 10;
  40. int result = binarySearch(arr, 0, n-1, x);
  41. (result == -1)? printf("Element is not present in array")
  42. : printf("Element is present at index %d", result);
  43. return 0;
  44. }

Insertion sort

算法思路:
// 对大小为n的数组arr[]进行升序排序(从小到大)
insertionSort(arr, n)
for i = 1 to n-1:
Pick element arr[i] and insert it into sorted sequence arr[0…i-1]

  1. /* Function to sort an array using insertion sort*/
  2. void insertionSort(int arr[], int n)
  3. {
  4. int i, key, j;
  5. for (i = 1; i < n; i++)
  6. {
  7. key = arr[i];//当前需要插入的元素.
  8. j = i-1;
  9. /* Move elements of arr[0..i-1], that are
  10. greater than key, to one position ahead
  11. of their current position */
  12. while (j >= 0 && arr[j] > key)
  13. {
  14. arr[j+1] = arr[j];
  15. j = j-1;
  16. }
  17. arr[j+1] = key;
  18. }
  19. }

Selection Sort

算法思路:
不断选择“未排序”数组中最小的元素,并把它放在数组的开头.

  1. void selectionSort(int arr[], int n)
  2. {
  3. int i, j, min_idx;
  4. // One by one move boundary of unsorted subarray
  5. for (i = 0; i < n-1; i++)
  6. {
  7. // Find the minimum element in unsorted array
  8. min_idx = i;
  9. for (j = i+1; j < n; j++)
  10. if (arr[j] < arr[min_idx])
  11. min_idx = j;
  12. // Swap the found minimum element with the first element
  13. swap(&arr[min_idx], &arr[i]);
  14. }
  15. }

Bubble Sort

算法思路:
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.

  1. /* A function to implement bubble sort */
  2. void bubbleSort(int arr[], int n)
  3. {
  4. int i, j;
  5. for (i = 0; i < n-1; i++)
  6. // Last i elements are already in place
  7. for (j = 0; j < n-i-1; j++)
  8. if (arr[j] > arr[j+1])
  9. swap(&arr[j], &arr[j+1]);
  10. }

Quick Sort

算法思路:
1、选择一个主元;
2、根据主元,将数组分成两部分:比主元小的部分和比主元大的部分;
3、递归地,分别对两个部分进行Quick Sort。

  1. /* This function takes last element as pivot, places
  2. the pivot element at its correct position in sorted
  3. array, and places all smaller (smaller than pivot)
  4. to left of pivot and all greater elements to right
  5. of pivot */
  6. int partition (int arr[], int low, int high)
  7. {
  8. int pivot = arr[high]; // pivot
  9. int i = (low - 1); // Index of smaller element
  10. for (int j = low; j <= high - 1; j++)
  11. {
  12. // If current element is smaller than or
  13. // equal to pivot
  14. if (arr[j] <= pivot)
  15. {
  16. i++; // increment index of smaller element
  17. swap(&arr[i], &arr[j]);
  18. }
  19. }
  20. swap(&arr[i + 1], &arr[high]);
  21. return (i + 1);
  22. }
  23. //另一种Partition
  24. int partition( int arr[], int low, int high) {
  25. int pivot = arr[low], i = low, j = high + 1;
  26. while( 1)
  27. {
  28. do ++i; while( arr[i] <= pivot && i <= high );
  29. do --j; while( arr[j] > pivot );
  30. if( i >= j ) break;
  31. swap(&arr[i], &arr[j]);
  32. }
  33. swap(&arr[low], &arr[j]);
  34. return j;
  35. }
  36. /* The main function that implements QuickSort
  37. arr[] --> Array to be sorted,
  38. low --> Starting index,
  39. high --> Ending index */
  40. void quickSort(int arr[], int low, int high)
  41. {
  42. if (low < high)
  43. {
  44. /* pi is partitioning index, arr[p] is now
  45. at right place */
  46. int pi = partition(arr, low, high);
  47. // Separately sort elements before
  48. // partition and after partition
  49. quickSort(arr, low, pi - 1);
  50. quickSort(arr, pi + 1, high);
  51. }
  52. }

参考资料

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注