---
# System prepended metadata

title: Untitled

---

首先我們先來改造qsort
把它變成比較好懂的樣子

```c
#include <stdio.h>

// A utility function to swap two elements 
void swap(int* a, int* b) 
{ 
    int t = *a; 
    *a = *b; 
    *b = t; 
} 
  
/* This function takes last element as pivot, places 
the pivot element at its correct position in sorted 
array, and places all smaller (smaller than pivot) 
to left of pivot and all greater elements to right 
of pivot */
int partition (int arr[], int low, int high) 
{ 
    int pivot = arr[high]; // pivot 
    int i = (low - 1); // Index of smaller element and indicates the right position of pivot found so far

    for (int j = low; j <= high - 1; j++)
    {
        // If current element is smaller than the pivot
        if (arr[j] < pivot)
        {
            i++; // increment index of smaller element
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
} 
  
/* The main function that implements QuickSort 
arr[] --> Array to be sorted, 
low --> Starting index, 
high --> Ending index */
void quickSort(int nums[], int firstnumber, int lastnumber) 
{ 
    if (firstnumber < lastnumber) 
    { 
        /* pi is partitioning index, arr[p] is now 
        at right place */
        int benchmark = partition(nums, firstnumber, lastnumber); 
  
        // Separately sort elements before 
        // partition and after partition 
        quickSort(nums, firstnumber, benchmark - 1); 
        quickSort(nums, benchmark + 1, lastnumber); 
    } 
} 
  
/* Function to print an array */
void printArray(int nums[], int numSize)
{
    int i;
    for (i = 0 ; i < numSize ; i++)
        printf("%d ", nums[i]);
    printf("\n");
}
  
int main() 
{ 
    int arr[] = {10, 7, 8, 9, 1, 5}; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    quickSort(arr, 0, n - 1); 
    printArray(arr, n); 
    return 0; 
}
```
透過不斷取基準值 去做 左右分堆的排序
然而這總算法會在 數字初始就是排好的情況爆炸
![](https://i.imgur.com/Dhp4vIb.png)
時間複雜度: nlogn ~ n平方
---------窩是分隔線-----------
再來來改造 bubblesort
```c
#include <stdio.h>
#define SIZE 10
// <<change random number array to 10 numbers>> 
int main(void) 
{   
   // <<set an array to make sure the sort still alive>>
   int nums[SIZE] = {2, 6, 4, 8, 10, 12, 89, 68, 45, 37}; 

   puts("Data items in original order");
   
   // <<use print to make sure we have an random array>>
   for (int first_out = 0; first_out < SIZE; first_out++ ) {
      printf("%4d", nums[first_out]);
   } 

   // <<bubble sort>>                                             
   for (unsigned int lastnum = 1 ; lastnum  < SIZE ; lastnum++ ) {                   
      // <<use lastnum to know how many number justified>>
      for (int locate = 0; locate < SIZE-lastnum; locate++) {                     
         // <<locate is which number we check now>>      
         if (nums[locate] > nums[locate + 1]) {
         	//<<hold can let the number be remember in a new place and use it to change number in diffrent array>>
            int hold = nums[locate];                                   
            nums[locate] = nums[locate + 1];                             
            nums[locate + 1] = hold;                               
         }                                       
      }                                   
   }                                      
   
   puts("\nData items in ascending order");

   // <<use print array to make sure sort can work >>
   for (int last_out = 0; last_out < SIZE; last_out++ ) {
      printf("%4d", nums[last_out]);
   }
   
   puts("");
}
```
然而這種手法當測資過多時 就會整個超時
![](https://i.imgur.com/Jh8bsp2.png)
時間複雜度:n平方
---------窩是分隔線-----------
再來來改造 insertionsort
```c 
#include <math.h>
#include <stdio.h>

/* Function to sort an array using insertion sort*/
void insertionSort(int nums[], int numsSize){
    int run, key, checkrun;
    for (run = 1; run < numsSize; run++) {
        key = nums[run];
        //first we take first number to be a reference value 
        checkrun = run - 1;
        //take number to compare number higher check it to left one number untile it be folder in left and right number
        while (checkrun >= 0 && nums[checkrun] > key) {
            nums[checkrun + 1] = nums[checkrun];
            checkrun = checkrun - 1;
        }
        // then take the next number to do it again
        nums[checkrun + 1] = key;
    }
}

// A utility function to print an array of size n
void printArray(int nums[], int numsSize)
{
    int i;
    for (i = 0; i < numsSize; i++)
        printf("%d ", nums[i]);
    printf("\n");
}

/* Driver program to test insertion sort */
int main()
{
    int nums[] = { 12, 11, 13, 5, 6 };
    int numsSize = sizeof(nums) / sizeof(nums[0]);

    insertionSort(nums, numsSize);
    printArray(nums, numsSize);

    return 0;
}
```
然而這種手法當測資過多時 就會整個超時
![](https://i.imgur.com/DHxpbc2.png)
時間複雜度:<n平方 但沒有小太多
---------窩是分隔線-----------
再來來改造 selectionsort
```c 
#include <stdio.h>


void swap(int *xp, int *yp)
{
	int temp = *xp;
	*xp = *yp;
	*yp = temp;
}

void selectionSort(int nums[], int digits)
{
	int run, check, smallnum;

	// <<run to keep running to check in array>> 
	for (run = 0; run < digits-1; run++)
	{
		// <<find the minimum num in the array>>
		smallnum = run;
		
		// <<when the number in the array we already arrange skip it>>
		for (check = run+1; check < digits; check++){
			if (nums[check] < nums[smallnum]){
					smallnum = check;
			}
		}
		// <<last change the minimum num to front of array(behind the array we already arrange)>>
		swap(&nums[smallnum], &nums[run]);
	}
}

/* Function to print an array */
void printArray(int nums[], int size)
{
	int i;
	for (i=0; i < size; i++)
		printf("%d ", nums[i]);
	printf("\n");
}

// Driver program to test above functions
int main()
{
	int nums[] = {64, 25, 12, 22, 11};
	int digits = sizeof(nums)/sizeof(nums[0]);
	selectionSort(nums, digits);
	printf("Sorted array: \n");
	printArray(nums, digits);
	return 0;
}
```
然而這種手法當測資過多時 就會整個超時
![](https://i.imgur.com/DfOeRWI.png)
時間複雜度: 不穩定
---------窩是分隔線-----------
再來來改造 mergesort
```c 
#include <stdio.h>
#include <stdlib.h>

void merge(int arr[], int l, int m, int r)
{
	int leftrun, rightrun, middleset;
	int left_gape = m - l + 1;
	int right_gape = r - m;

	//create two array left and right
	int LEFT[left_gape], RIGHT[right_gape];

  	// put somethin in left and right array
	for (leftrun = 0; leftrun < left_gape; leftrun++)
		LEFT[leftrun] = arr[l + leftrun];
	for (rightrun = 0; rightrun < right_gape; rightrun++)
		RIGHT[rightrun] = arr[m + 1 + rightrun];

	//check which is the minimum put it in first gape
	leftrun = 0; 
	rightrun = 0; 
	middleset = l; 
	while (leftrun < left_gape && rightrun < right_gape) {
		if (LEFT[leftrun] <= RIGHT[rightrun]) {
			arr[middleset] = LEFT[leftrun];
			leftrun++;
		}
		else {
			arr[middleset] = RIGHT[rightrun];
			rightrun++;
		}
		middleset++;
	}

	/* Copy the remaining elements of L[], if there
	are any */
	while (leftrun < left_gape) {
		arr[middleset] = LEFT[leftrun];
		leftrun++;
		middleset++;
	}

	/* Copy the remaining elements of R[], if there
	are any */
	while (rightrun < right_gape) {
		arr[middleset] = RIGHT[rightrun];
		rightrun++;
		middleset++;
	}
}


void mergeSort(int nums[], int left, int right)
{
	if (left < right) {

		int middle = left + (right - left) / 2;

		// put they in to diffrent side of an array
		mergeSort(nums, left, middle);
		mergeSort(nums, middle + 1, right);

		merge(nums, left, middle, right);
	}
}

/* UTILITY FUNCTIONS */
/* Function to print an array */
void printArray(int A[], int size)
{
	int i;
	for (i = 0; i < size; i++)
		printf("%d ", A[i]);
	printf("\n");
}

/* Driver code */
int main()
{
	int nums[] = { 12, 11, 13, 5, 6, 7 };
	int numsSize = sizeof(nums) / sizeof(nums[0]);

	printf("Given array is \n");
	printArray(nums, numsSize);
	int left = 0 , right = numsSize - 1;
	mergeSort(nums, left, right);

	printf("\nSorted array is \n");
	printArray(nums, numsSize);
	return 0;
}
```
![](https://i.imgur.com/RA4SjEz.png)
時間複雜度相對穩定的算法
時間複雜度 nlogn
---------窩是分隔線-----------
同場加映: 函式庫裡面的 qsort 2.0(呼叫函式庫)
```c 
#include <stdio.h>
#include <stdlib.h>
int check(const void*a,const void*b)
{
    return (*(int*)a - *(int*)b);
}

int main(void)
{
    int arr[] = { 1, 4, 2, 3, 5};
    int arrsize=sizeof(arr)/sizeof(int);
    qsort(arr,arrsize,sizeof(int),check);
    int i=0;
	while (i != arrsize)
    {
        printf("%d ",arr[i]);
        i++;
    }
    return 0;
}
```
窩也不知道為什麼 這個丟leet code 會過
![](https://i.imgur.com/hiSMc2A.png)

