数据结构-链表排序(冒泡，选择，插入，快速，归并)

1.冒泡排序

        基本思想: 把第一个元素与第二个元素比较，如果第一个比第二个大，则交换他们的位置。接着继续比较第二个与第三个元素，如果第二个比第三个大，则交换他们的位置… 我们对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样一趟比较交换下来之后，排在最右的元素就会 是最大的数。除去最右的元素，我们对剩余的元素做同样的工作，如此重复下去，直到排序完成。

        具体步骤：   

• 1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。   
• 2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。   
• 3.针对所有的元素重复以上的步骤，除了最后一个。   
• 4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

          时间复杂度：O(N2)

          空间复杂度：O(1) 

  Node *BubbleSort(Node *phead)
  {
  	Node * p = phead;
  	Node * q = phead->next;
  	/*有几个数据就-1；比如x 个idata>q->data)
  			{
  				/*头结点和下一节点的交换，要特殊处理，更新新的头head*/
  				if (p == phead)
  				{
  					p->next = q->next;
  					q->next = p;
  					head = q;
  					phead = q;
  					/*这里切记要把p,q换回来，正常的话q应该在p的前面，进行的是p,q的比较
  					*但是经过指针域交换之后就变成q,p.再次进行下一次比较时，
  					*就会变成q,p的数据域比较。假如原本p->data > q->data,则进行交换。变成q->data和p->data比较，
  					*不会进行交换，所以排序就会错误。有兴趣的可以调试下。
  					*/	
  					Node*temp=p; 
  					p=q;
  					q=temp;		
  				}
  				/*处理中间过程，其他数据的交换情况，要寻找前驱节点if (p != phead)*/
  				else 
  				{
  					/*p，q的那个在前，那个在后。指针域的连接画图好理解一点*/
  					if (p->next == q)
  					{
  						/*寻找p的前驱节点*/
  						Node *ppre = FindPreNode(p);
  						/*将p的下一个指向q的下一个*/
  						p->next = q->next;
  						/*此时q为头结点，让q的下一个指向p，连接起来*/
  						q->next = p;
  						/*将原来p的前驱节点指向现在的q，现在的q为头结点*/
  						ppre->next = q;
  						Node*temp=p; 
  						p=q; 
  						q=temp;
  					}
  					else if (q->next == p)
  					{
  						Node *qpre = FindPreNode(q);
  						q->next = p->next;
  						p->next = q;
  						qpre->next = p;
  						Node*temp=p;
  						p=q; 
  						q=temp;
  						}									
  				}		
  			}
  			/*地址移动*/
  			p = p->next;
  			q = q->next;
  		}
  		/*进行完一轮比较后，从头开始进行第二轮*/
  		p = phead;
  		q = phead->next;	
  	}
  	
  	head = phead;
  	return head;
  }

  2.快速排序

          基本思想 ：我们从数组中选择一个元素，我们把这个元素称之为中轴元素吧，然后把数组中所有小于中轴元素的元素放在其左边， 所有大于或等于中轴元素的元素放在其右边，显然，此时中轴元素所处的位置的是有序的。也就是说，我们无需再移动中轴 元素的位置。   从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素)，接着我们通过递归的方式，让中轴元素 左边的数组和右边的数组也重复同样的操作，直到数组的大小为1，此时每个元素都处于有序的位置。

          具体步骤：   

  • 1.从数列中挑出一个元素，称为 “基准”（pivot）;   
  • 2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；   
  • 3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

            时间复杂度：O(NlogN)

            空间复杂度：O(logN) 

    int *QuickSort(Node* pBegin, Node* pEnd)
    {
        if(pBegin == NULL || pEnd == NULL || pBegin == pEnd)
            return 0;
     
        //定义两个指针
        Node* p1 = pBegin;
        Node* p2 = pBegin->next;
        int pivot = pBegin->data;
    	//每次只比较小的，把小的放在前面。经过一轮比较后，被分成左右两部分。其中p1指向中值处，pbegin为pivot。
        while(p2 != NULL)/* && p2 != pEnd->next */
    	{
            if(p2->data < pivot)
    		{
                p1 = p1->next;
                if(p1 != p2)
    			{
                    SwapData(&p1->data, &p2->data);
            	}
          	}
            p2 = p2->next;
       }
       /*此时pivot并不在中间，我们要把他放到中间，以他为基准，把数据分为左右两边*/
        SwapData(&p1->data, &pBegin->data);
        //此时p1是中值节点
    	//if(p1->data >pBegin->data)
        QuickSort(pBegin, p1);
    	//if(p1->data < pEnd->data)
        QuickSort(p1->next, pEnd);
    }

    3.插入排序

            基本思想：每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。

            具体步骤：   

    • 1.将待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列；   
    • 2.取出下一个元素，在已经排序的元素序列中从后向前扫描；   
    • 3.如果该元素（已排序）大于新元素，将该元素移到下一位置；   
    • 4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；   
    • 5.将新元素插入到该位置后；   
    • 6.重复步骤2~5。

              时间复杂度：O(N2)

              空间复杂度：O(1)

      struct ListNode *insertionSortList(struct ListNode *head) {
          if (head == NULL) { // 如果链表为空，直接返回
              return head;
          }
          // 创建哑节点
          struct ListNode *dummyHead = malloc(sizeof(struct ListNode));
          dummyHead->val = 0;
          dummyHead->next = head;
          // lastSorted 指向已经排序好的链表的最后一个节点
          struct ListNode *lastSorted = head;
          // curr 指向待排序的节点
          struct ListNode *curr = head->next;
          while (curr != NULL) {
              if (lastSorted->val <= curr->val) { // 如果待排序节点大于等于已排序链表的最后一个节点，直接将lastSorted向后移动一位
                  lastSorted = lastSorted->next;
              } else { // 否则，需要找到插入的位置
                  struct ListNode *prev = dummyHead;
                  // 寻找插入位置，找到第一个大于当前节点值的节点的前一个节点
                  while (prev->next->val <= curr->val) {
                      prev = prev->next;
                  }
                  // 将curr插入到prev之后
                  lastSorted->next = curr->next;
                  curr->next = prev->next;
                  prev->next = curr;
              }
              // 移动curr指针到下一个待排序节点
              curr = lastSorted->next;
          }
          // 返回排序后的链表
          return dummyHead->next;
      }

      4.选择排序

              基本思想：首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置(如果第一个元素就是最小元素那么它就和自己交换)。其次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这种方法我们称之为选择排序。         具体步骤：   

      • 1.首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。   
      • 2.再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。   
      • 3.重复第二步，直到所有元素均排序完毕。

                时间复杂度：O(N2)

                空间复杂度：O(1)

        在这里插入图片描述

        Node* SelectSort(Node* phead) 
        {               
        	Node *temp;
        	Node *temphead = phead;
        	/*将第一次的最大值设置为头结点*/
        	int max = phead->data;
        	/*交换变量*/
        	 for(int i = 0;idata;
        		while (temphead->next !=NULL)
        		{
        			/*寻找最大值*/
        			if(max < temphead->next->data)
        			{
        				max =  temphead->next->data;
        			}
        			/*移动指针位置*/
        			temphead = temphead->next;
        		}	
        		/*找到最大值的位置*/
        		temp = FindList(max);
        		/*判断最大值是否和头节点相同*/
        		if(phead != temp)
        		{
        			SwapNode(phead,temp);//交换节点		
        		}
        		/*更新下一次遍历的头结点*/
        		temphead = temp->next;
        		phead = temphead;
        	 }
        } 

        5.归并排序

                基本思想：归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法： 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）； 自下而上的迭代；

                具体步骤：   

        • 1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；   
        • 2.设定两个指针，最初位置分别为两个已经排序序列的起始位置；   
        • 3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置； 
        • 4.重复步骤 3 直到某一指针达到序列尾；   
        • 5.将另一序列剩下的所有元素直接复制到合并序列尾。

                  时间复杂度：O(NlogN)

                  空间复杂度：O(N) 

          //找到链表中间节点
          struct ListNode* findMiddle(struct ListNode* head) {
              if (head == NULL || head->next == NULL) {
                  return head;
              }
              struct ListNode* slow = head;
              struct ListNode* fast = head->next->next;
              while (fast != NULL && fast->next != NULL) {
                  slow = slow->next;
                  fast = fast->next->next;
              }
              return slow;
          }
          //合并两个有序链表
          struct ListNode* mergeList(struct ListNode* left, struct ListNode* right) {
              struct ListNode* dummy = malloc(sizeof(struct ListNode));
              struct ListNode* temp = dummy;
              while (left != NULL && right != NULL) {
                  if (left->val <= right->val) {
                      temp->next = left;
                      left = left->next;
                  }
                  else if (left->val > right->val) {
                      temp->next = right;
                      right = right->next;
                  }
                  temp = temp->next;
              }
              temp->next = left != NULL ? left : right;
              return dummy->next;
          }
          struct ListNode* sortList(struct ListNode* head) {
              //递归结束条件
              if (head == NULL || head->next == NULL) {
                  return head;
              }
              //找到链表中间节点并断开链表 & 递归下探
              struct ListNode* middle = findMiddle(head);
              struct ListNode* rightHead = middle->next;
              middle->next = NULL;
              struct ListNode* left = sortList(head);
              struct ListNode* right = sortList(rightHead);
              //合并有序链表
              return mergeList(left, right);
          }